哈希優(yōu)化策略

在算法題中，我們常通過將線性查找替換為哈希查找來降低算法的時間復雜度。我們借助一個算法題來加深理解。

Question

給定一個整數(shù)數(shù)組 nums 和一個目標元素 target ，請在數(shù)組中搜索“和”為 target 的兩個元素，并返回它們的數(shù)組索引。返回任意一個解即可。

線性查找：以時間換空間

考慮直接遍歷所有可能的組合。如圖 10-9 所示，我們開啟一個兩層循環(huán)，在每輪中判斷兩個整數(shù)的和是否為 target ，若是則返回它們的索引。

圖 10-9   線性查找求解兩數(shù)之和

two_sum.cpp

/* 方法一：暴力枚舉 */
vector<int> twoSumBruteForce(vector<int> &nums, int target) {
    int size = nums.size();
    // 兩層循環(huán)，時間復雜度 O(n^2)
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size; j++) {
            if (nums[i] + nums[j] == target)
                return {i, j};
        }
    }
    return {};
}

此方法的時間復雜度為 $?\left({?}^2\right)$O(n2) ，空間復雜度為 O(1)$?\left(1\right)$ ，在大數(shù)據(jù)量下非常耗時。

哈希查找：以空間換時間?

考慮借助一個哈希表，鍵值對分別為數(shù)組元素和元素索引。循環(huán)遍歷數(shù)組，每輪執(zhí)行圖 10-10 所示的步驟。

1. 判斷數(shù)字 target - nums[i] 是否在哈希表中，若是則直接返回這兩個元素的索引。
2. 將鍵值對 nums[i] 和索引 i 添加進哈希表。

圖 10-10   輔助哈希表求解兩數(shù)之和

實現(xiàn)代碼如下所示，僅需單層循環(huán)即可。

two_sum.cpp

/* 方法二：輔助哈希表 */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
    int size = nums.size();
    // 輔助哈希表，空間復雜度 O(n)
    unordered_map<int, int> dic;
    // 單層循環(huán)，時間復雜度 O(n)
    for (int i = 0; i < size; i++) {
        if (dic.find(target - nums[i]) != dic.end()) {
            return {dic[target - nums[i]], i};
        }
        dic.emplace(nums[i], i);
    }
    return {};
}

此方法通過哈希查找將時間復雜度從 O(n2) 降低至 O(n) ，大幅提升運行效率。

由于需要維護一個額外的哈希表，因此空間復雜度為 O(n) 。盡管如此，該方法的整體時空效率更為均衡，因此它是本題的最優(yōu)解法。