哈希優(yōu)化策略

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

Question

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)元素 target ，請(qǐng)?jiān)跀?shù)組中搜索“和”為 target 的兩個(gè)元素，并返回它們的數(shù)組索引。返回任意一個(gè)解即可。

線性查找：以時(shí)間換空間

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

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

two_sum.cpp

/* 方法一：暴力枚舉 */
vector<int> twoSumBruteForce(vector<int> &nums, int target) {
    int size = nums.size();
    // 兩層循環(huán)，時(shí)間復(fù)雜度 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 {};
}

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

哈希查找：以空間換時(shí)間?

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

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

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

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

two_sum.cpp

/* 方法二：輔助哈希表 */
vector<int> twoSumHashTable(vector<int> &nums, int target) {
    int size = nums.size();
    // 輔助哈希表，空間復(fù)雜度 O(n)
    unordered_map<int, int> dic;
    // 單層循環(huán)，時(shí)間復(fù)雜度 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 {};
}

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

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