hash 表、快排與二分查找：兩數之和

大家好，我是小風哥。

我在這個公衆號寫過很多計算機底層方向的文章，應許多讀者的要求，從這篇文章起我們開始一個新的系列：數據結構與算法，原來的計算機底層方向也會繼續更新。

數據結構與算法系列的前期以 LeetCode 題解爲例來講解，當到達一定量後總結程序員必備的算法思想以及必備的數據結構知識，這個系列的目的是讓你：看得懂、學得會、寫得出。

也歡迎大家在留言區打卡，準備春招的同學可以一起刷起來。

廢話少說，開始今天的題目，這是數據結構與算法之 LeetCode 刷題系列第 1 篇。

今天的題目是兩數之和，題目是這樣的：

給定一個整數數組與一個 target，在數組中找到兩個數，其和等於 target，並返回這兩個數字的下標。

示例：

數組 nums = [2,7,11,15], target = 9，則輸出 [0,1]，因爲 nums[0] + nums[1] == 9

題目不難，解決方法也有很多種，我們依次來看一下，任何題目都可以從最簡單的方法開始去想，以下代碼均爲 C++。

暴力解法

我們首先固定一個數字，比如第一個數字 2，然後遍歷後面的元素，判斷是否相加等於 9，有就記錄下來，沒有則看下一個數字，也就是 7，最終代碼非常簡單，其時間複雜度爲 O(n^2)：

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                res.push_back(i);
                res.push_back(j);
            }
        }
    }
    return res;
}

萬萬沒想到的是這樣的代碼竟然可以 AC（AC 是刷題的常用術語，也就是 Accept，通過代碼的評測標準，包括正確性、耗時、內存的消耗等等）。

從這裏的分析我們其實可以知道，這本質上其實是一個搜索問題，假如我知道第一個數字是 2，而 target 是 9，那麼我們需要回答 “這個數組中是否有 7 這個數字”，因此這本質上是一個搜索問題。

既然是搜索問題，那麼 hash 表顯然是我們最得力的武器。

hash 表

關於 hash 表後續會有專題詳解。

C++ 中基於 hash 表這種數據結構的是 std::unordered_map，我們的思路也很簡單，把所有的數組元素作爲 key，數組下標作爲值，因爲題目要求我們返回下標，因此這裏必須把下標也存儲起來，有了這樣的 map，剩下的就簡單了。

依次遍歷數組中每個元素 N，查找 target-N 是否存在於 map 中即可。

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;
    vector<int> res;

    for (int i = 0; i < nums.size(); i++) {
        auto iter = map.find(target - nums[i]);
        if (iter == map.end()) {
            map[nums[i]] = i;
        } else {
            res.push_back(i);
            res.push_back(iter->second);
        }
    }
    return res;
}

顯然，該算法時間複雜度是 O(n)，因爲一般情況下可以認爲 hash 表能常數複雜度下查找到元素。

是不是覺得很簡單，注意，這裏使用了 map 容器，那如果面試官要求你不得藉助這種已經寫的庫該怎麼辦呢？

我們在文章開頭分析過，這其實本質上是一個搜索問題，既然是搜索問題，那麼解決該問題的另一種思路就是排序。

只要排好序剩下的就簡單了，二分查找天然就是有序搜索問題的好幫手。

因此接下來的思路就是排序加二分查找。

排序加二分查找

思路已經介紹完畢，接下來我們手寫快排，但是我們排誰呢？

注意題目要求返回元素下標，因此排序時需要除了數組元素也需要把下標帶上。

void quick_sort(vector<pair<int,int>>& nums, int b, int e) {
    if (b > e) return;

    int i = b - 1;
    for (int k = b; k < e; k++) {
        if (nums[k].second < nums[e].second) {
            swap(nums[++i], nums[k]);
        }
    }
    swap(nums[++i], nums[e]);
    quick_sort(nums, b, i - 1);
    quick_sort(nums, i + 1, e);
}

有的同學可能沒有看懂這裏的排序方法，甚至認爲快排之類的排序算法只能靠死記硬背，其實不是的，這類經典的排序算法背後都有極其重要的算法思想，比如快排背後的思想其實是 divide and conquer，這是另一個龐大的話題，限於篇幅，我們會在後續專題詳解。

現在快排有了，接下來實現二分查找：

int binary_search(vector<pair<int,int>>& nums,
                  int b, int e, int target) {
    while(b <= e) {
        int m = (b + e) / 2;
        if (nums[m].second == target) {
            return nums[m].first;
        } else if (nums[m].second < target) {
            b = m + 1;
        } else {
            e = m - 1;
        }
    }
    return -1;
}

二分查找是一個看起來極其容易但寫起來卻極其容易出錯的算法，不信你可以試試看，這裏暫時還不打算詳細講解二分，後續還會多次遇到這個算法，當我們積攢了足夠多的示例後將系統介紹這裏涉及的快排與二分。

有了這些函數後就可以實現主要邏輯了：

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    vector<pair<int, int>> nums_index;
    int size = nums.size();

    for (int i = 0; i < size; i++) {
        nums_index.push_back(pair<int, int>(i, nums[i]));
    }

    quick_sort(nums_index, 0, size - 1);

    for (int i = 0; i < size - 1; i++) {
        int r = binary_search(nums_index, i + 1, size - 1,
                              target - nums_index[i].second);
        if (r != -1) {
            res.push_back(nums_index[i].first);
            res.push_back(r);
        }
    }
    return res;
}

運行一下發現耗時 1s 左右，雖然也可以 AC，但可以看到運行速度其實是很慢的，還是 hash 表這種解法速度最快。

可以看到，一道題目其實有很多解法，這裏涉及到 hash、快排與二分查找，後續我們還會多次見到這些方法，而我們在積攢足夠多的示例後會系統性講解這些數據結構與算法。

小風哥之前講解的計算機底層文章已經全部彙總在了這裏:https://github.com/xfenglu/everycodershouldknow, 歡迎 star 提 issue。

也歡迎大家添加我的微信 coder_saver 圍觀朋友圈，備註寫 “圍觀” 二字即可，一起見證我們的成長。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/9YeqWF7Zds-TCYQgM0BccA