DAY 2 試題

問題描述

這題是 LeetCode 上非常經典的問題之一「兩數之和」（Two Sum）。給定一個整數陣列 nums 和一個目標值 target，我們需要找到陣列中兩個數，使得它們的和等於 target，並返回這兩個數字的索引。 這題要求每個數字只能使用一次，並且假設每個輸入只會有唯一解。
比如:nums = [2,7,11,15], target = 9 正確是 [0,1]。因為nums[0] + nums[1] == 9。

解題思路

我們可以使用暴力法來檢查每個數字與其他數字的組合，但這樣的時間複雜度為 O(n²)，當陣列很大時效率低下。因此，我們需要優化解法。

優化的關鍵是利用 哈希表（unordered_map）。通過哈希表，我們能夠在 O(1) 的時間內找到目標數字的補數。
具體步驟如下：

1. 建立哈希表：哈希表的鍵是陣列中的數字，值是數字的索引。這樣我們可以快速查詢是否存在一個數字能與當前數字加起來等於 target。
2. 遍歷陣列：對於每一個數字，計算它與 target 的差值（即補數），並檢查這個補數是否已經在哈希表中。如果找到了補數，則返回其索引與當前數字的索引。
3. 存入當前數字：如果沒找到補數，則將當前數字與其索引存入哈希表，以備後續查找。

解題過程如下:

class Solution {
public:
    // 成員函數，實現 twoSum 邏輯
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num_map;  // 哈希表來存儲數字及其索引

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];  // 計算目標值減去當前數字的補數

            // 檢查補數是否在哈希表中
            if (num_map.find(complement) != num_map.end()) {
                return {num_map[complement], i};  // 找到結果，返回補數和當前數字的索引
            }

            // 如果補數不存在，將當前數字存入哈希表
            num_map[nums[i]] = i;
        }

        return {};  // 根據題意，假設必有解，因此這行不會執行
    }
};

Hash Table介紹

哈希表（Hash Table）是一種非常高效的數據結構，它通過使用哈希函數來實現快速的查找、插入和刪除操作。哈希表在解決查詢問題（例如尋找一個數字是否存在、找出兩數之和等問題）時有非常廣泛的應用，因為它能夠將時間複雜度降低到 O(1)。

哈希表的基本概念

1. 哈希函數：

• 哈希函數是一個將輸入（鍵）映射到哈希表中一個具體位置（桶）的函數。這個位置稱為該鍵的 哈希值。哈希函數的作用是將數據根據某種規則轉換為一個整數，這個整數對應到哈希表中的索引位置。
• 哈希函數需要具備的兩個基本特點是快速計算和均勻分布，以減少不同鍵映射到相同位置（即哈希衝突）的可能性。

2. 哈希衝突：

• 當兩個不同的鍵經過哈希函數計算後，映射到哈希表的同一位置，這稱為哈希衝突。哈希衝突是無法完全避免的，為了處理哈希衝突，常見的解決方法有：
• 鏈地址法（Separate Chaining）：每個哈希表的桶存儲一個鏈表，當哈希衝突發生時，新的元素會被添加到這個桶中的鏈表中。
• 開放地址法（Open Addressing）：當哈希衝突發生時，嘗試找到另一個空桶來存儲衝突的元素。

3. 負載因子：

• 負載因子（Load Factor）是哈希表中已經存儲的元素數量與哈希表總大小的比值。負載因子越大，哈希衝突的可能性越高，性能也會因此下降。因此當負載因子達到一定程度後，哈希表會動態擴展。

結論:哈希表是一種非常高效的數據結構，特別適合需要頻繁查找、插入和刪除操作的場景。C++ 中的 unordered_map 是其實現之一，提供了簡單易用的接口和高效的操作。雖然存在哈希衝突的問題，但通過合理選擇哈希函數和調整負載因子，哈希表在大多數情況下仍然能保持極高的性能。

以上是第二天的自學內容分享，謝謝大家。