10.8 雜湊表

雜湊表（hash table, hash map），又稱散列表，使用 $O(n)$ 空間複雜度儲存資料，通過雜湊函數（hash function）映射位置，從而實現近似 $O(1)$ 時間複雜度的插入、查詢、刪除等操作。雜湊表可以用來統計頻率、記錄內容等等。

如果元素是有限的，且範圍不大，那麼可以用一個固定大小的陣列來儲存或統計元素。例如，我們需要統計一個字串中所有字母的出現次數，則可以用一個長度為 26 的陣列來進行統計，其雜湊函數即為字母在字母表中的位置，這樣空間複雜度就可以降低為常數。

1. Two Sum

題目描述

給定一個（未排序的）整數陣列，已知有且只有兩個數的和等於給定值，求這兩個數的位置。

輸入輸出範例

輸入是一個一維整數陣列和一個目標值，輸出是一個大小為 2 的一維陣列，表示滿足條件的兩個數字的位置。

Input: nums = [2, 7, 15, 11], target = 9
Output: [0, 1]

在這個範例中，第 0 個位置的值 2 和第 1 個位置的值 7 的和為 9。

題解

我們可以利用雜湊表儲存遍歷過的值以及它們的位置，每次遍歷到位置 i 的時候，查找雜湊表裡是否存在 target - nums[i]，若存在，則說明這兩個值的和為 target。

C++

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> cache;  // <值，位置>
    for (int i = 0; i < nums.size(); ++i) {
        int num1 = nums[i], num2 = target - num1;
        if (cache.contains(num2)) {
            return vector<int>{cache[num2], i};
        }
        cache[num1] = i;
    }
    return {};
}

Python

def twoSum(nums: List[int], target: int) -> List[int]:
    cache = dict() # <值，位置>
    for i, num1 in enumerate(nums):
        num2 = target - num1
        if num2 in cache:
            return [cache[num2], i]
        cache[num1] = i
    return []

128. Longest Consecutive Sequence

題目描述

給定一個整數陣列，求這個陣列中的數字可以組成的最長連續序列有多長。

輸入輸出範例

輸入是一個整數陣列，輸出是一個整數，表示連續序列的長度。

Input: [100, 4, 200, 1, 3, 2]
Output: 4

在這個範例中，最長連續序列是 [1,2,3,4]。

題解

我們可以把所有數字放到一個雜湊表，然後不斷地從雜湊表中任意取一個值，並刪除掉其之前之後的所有連續數字，然後更新目前的最長連續序列長度。重複這一過程，我們就可以找到所有的連續數字序列。

C++

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> cache(nums.begin(), nums.end());
    int max_len = 0;
    while (!cache.empty()) {
        int cur = *(cache.begin());
        cache.erase(cur);
        int l = cur - 1, r = cur + 1;
        while (cache.contains(l)) {
            cache.erase(l--);
        }
        while (cache.contains(r)) {
            cache.erase(r++);
        }
        max_len = max(max_len, r - l - 1);
    }
    return max_len;
}

Python

def longestConsecutive(nums: List[int]) -> int:
    cache = set(nums)
    max_len = 0

    while len(cache) > 0:
        cur = next(iter(cache))
        cache.remove(cur)

        l, r = cur - 1, cur + 1
        while l in cache:
            cache.remove(l)
            l -= 1
        while r in cache:
            cache.remove(r)
            r += 1

        max_len = max(max_len, r - l - 1)

    return max_len

149. Max Points on a Line

題目描述

給定一些二維座標中的點，求同一條線上最多有多少點。

輸入輸出範例

輸入是一個二維整數陣列，表示每個點的橫縱座標；輸出是一個整數，表示滿足條件的最多點數。

Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
Output: 4

在這個範例中，$y = 5 - x$ 上有四個點。

題解

對於每個點，我們對其他點建立雜湊表，統計同一斜率的點一共有多少個。這裡利用的原理是，一條線可以由一個點和斜率唯一確定。此外，也需要考慮斜率不存在和重複座標的情況。

本題還利用了一個小技巧：在遍歷每個點時，對於陣列中位置 i 的點，我們只需要考慮 i 之後的點即可，因為 i 之前的點已經考慮過 i 了。

C++

int maxPoints(vector<vector<int>>& points) {
    int max_count = 0, n = points.size();
    for (int i = 0; i < n; ++i) {
        unordered_map<double, int> cache;  // <斜率, 點的數量>
        int same_xy = 1, same_y = 1;
        for (int j = i + 1; j < n; ++j) {
            if (points[i][1] == points[j][1]) {
                ++same_y;
                if (points[i][0] == points[j][0]) {
                    ++same_xy;
                }
            } else {
                double dx = points[i][0] - points[j][0],
                       dy = points[i][1] - points[j][1];
                ++cache[dx / dy];
            }
        }
        max_count = max(max_count, same_y);
        for (auto item : cache) {
            max_count = max(max_count, same_xy + item.second);
        }
    }
    return max_count;
}

Python

def maxPoints(points: List[List[int]]) -> int:
    max_count, n = 0, len(points)
    
    for i, point1 in enumerate(points):
        cache = dict()  # <斜率, 點的數量>
        same_xy, same_y = 1, 1
        
        for point2 in points[i + 1:]:
            if point1[1] == point2[1]:
                same_y += 1
            if point1[0] == point2[0]:
                same_xy += 1
            else:
                dx, dy = point1[0] - point2[0], point1[1] - point2[1]
                cache[dx / dy] = cache.get(dx / dy, 0) + 1

        max_count = max(max_count, same_y)
        for count in cache.values():
            max_count = max(max_count, same_xy + count)
    
    return max_count