大家好，我是小風(fēng)哥。

我在這個(gè)公眾號(hào)寫(xiě)過(guò)很多計(jì)算機(jī)底層方向的文章，應(yīng)許多讀者的要求，從這篇文章起我們開(kāi)始一個(gè)新的系列：數(shù)據(jù)結(jié)構(gòu)與算法，原來(lái)的計(jì)算機(jī)底層方向也會(huì)繼續(xù)更新。

數(shù)據(jù)結(jié)構(gòu)與算法系列的前期以L(fǎng)eetCode題解為例來(lái)講解，當(dāng)?shù)竭_(dá)一定量后總結(jié)程序員必備的算法思想以及必備的數(shù)據(jù)結(jié)構(gòu)知識(shí)，這個(gè)系列的目的是讓你：看得懂、學(xué)得會(huì)、寫(xiě)得出。

也歡迎大家在留言區(qū)打卡，準(zhǔn)備春招的同學(xué)可以一起刷起來(lái)。

廢話(huà)少說(shuō)，開(kāi)始今天的題目，這是數(shù)據(jù)結(jié)構(gòu)與算法之LeetCode刷題系列第1篇。

今天的題目是兩數(shù)之和，題目是這樣的：

給定一個(gè)整數(shù)數(shù)組與一個(gè)target，在數(shù)組中找到兩個(gè)數(shù)，其和等于target，并返回這兩個(gè)數(shù)字的下標(biāo)。

示例：

數(shù)組 nums = [2,7,11,15], target = 9，則輸出[0,1]，因?yàn)閚ums[0] + nums[1] == 9

題目不難，解決方法也有很多種，我們依次來(lái)看一下，任何題目都可以從最簡(jiǎn)單的方法開(kāi)始去想，以下代碼均為C++。

暴力解法

我們首先固定一個(gè)數(shù)字，比如第一個(gè)數(shù)字2，然后遍歷后面的元素，判斷是否相加等于9，有就記錄下來(lái)，沒(méi)有則看下一個(gè)數(shù)字，也就是7，最終代碼非常簡(jiǎn)單，其時(shí)間復(fù)雜度為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;
}

萬(wàn)萬(wàn)沒(méi)想到的是這樣的代碼竟然可以AC(AC是刷題的常用術(shù)語(yǔ)，也就是Accept，通過(guò)代碼的評(píng)測(cè)標(biāo)準(zhǔn)，包括正確性、耗時(shí)、內(nèi)存的消耗等等)。

從這里的分析我們其實(shí)可以知道，這本質(zhì)上其實(shí)是一個(gè)搜索問(wèn)題，假如我知道第一個(gè)數(shù)字是2，而target是9，那么我們需要回答“這個(gè)數(shù)組中是否有7這個(gè)數(shù)字”，因此這本質(zhì)上是一個(gè)搜索問(wèn)題。

既然是搜索問(wèn)題，那么hash表顯然是我們最得力的武器。

hash 表

關(guān)于hash表后續(xù)會(huì)有專(zhuān)題詳解。

C++中基于hash表這種數(shù)據(jù)結(jié)構(gòu)的是std::unordered_map，我們的思路也很簡(jiǎn)單，把所有的數(shù)組元素作為key，數(shù)組下標(biāo)作為值，因?yàn)轭}目要求我們返回下標(biāo)，因此這里必須把下標(biāo)也存儲(chǔ)起來(lái)，有了這樣的map，剩下的就簡(jiǎn)單了。

依次遍歷數(shù)組中每個(gè)元素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;
}

顯然，該算法時(shí)間復(fù)雜度是O(n)，因?yàn)橐话闱闆r下可以認(rèn)為hash表能常數(shù)復(fù)雜度下查找到元素。

是不是覺(jué)得很簡(jiǎn)單，注意，這里使用了map容器，那如果面試官要求你不得借助這種已經(jīng)寫(xiě)的庫(kù)該怎么辦呢?

我們?cè)谖恼麻_(kāi)頭分析過(guò)，這其實(shí)本質(zhì)上是一個(gè)搜索問(wèn)題，既然是搜索問(wèn)題，那么解決該問(wèn)題的另一種思路就是排序。

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

因此接下來(lái)的思路就是排序加二分查找。

排序加二分查找

思路已經(jīng)介紹完畢，接下來(lái)我們手寫(xiě)快排，但是我們排誰(shuí)呢?

注意題目要求返回元素下標(biāo)，因此排序時(shí)需要除了數(shù)組元素也需要把下標(biāo)帶上。

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);
}

有的同學(xué)可能沒(méi)有看懂這里的排序方法，甚至認(rèn)為快排之類(lèi)的排序算法只能靠死記硬背，其實(shí)不是的，這類(lèi)經(jīng)典的排序算法背后都有極其重要的算法思想，比如快排背后的思想其實(shí)是divide and conquer，這是另一個(gè)龐大的話(huà)題，限于篇幅，我們會(huì)在后續(xù)專(zhuān)題詳解。

現(xiàn)在快排有了，接下來(lái)實(shí)現(xiàn)二分查找：

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;
}

二分查找是一個(gè)看起來(lái)極其容易但寫(xiě)起來(lái)卻極其容易出錯(cuò)的算法，不信你可以試試看，這里暫時(shí)還不打算詳細(xì)講解二分，后續(xù)還會(huì)多次遇到這個(gè)算法，當(dāng)我們積攢了足夠多的示例后將系統(tǒng)介紹這里涉及的快排與二分。

有了這些函數(shù)后就可以實(shí)現(xiàn)主要邏輯了：

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;
}

運(yùn)行一下發(fā)現(xiàn)耗時(shí)1s左右，雖然也可以AC，但可以看到運(yùn)行速度其實(shí)是很慢的，還是hash表這種解法速度最快。

可以看到，一道題目其實(shí)有很多解法，這里涉及到hash、快排與二分查找，后續(xù)我們還會(huì)多次見(jiàn)到這些方法，而我們?cè)诜e攢足夠多的示例后會(huì)系統(tǒng)性講解這些數(shù)據(jù)結(jié)構(gòu)與算法。

本文轉(zhuǎn)載自微信公眾號(hào)「碼農(nóng)的荒島求生」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系碼農(nóng)的荒島求生公眾號(hào)。