作者丨碼農(nóng)的荒島求生
來源丨碼農(nóng)的荒島求生（ID：escape-it）
大家好，我是小風(fēng)哥。
我在這個公眾號寫過很多計(jì)算機(jī)底層方向的文章，應(yīng)許多讀者的要求，從這篇文章起我們開始一個新的系列：數(shù)據(jù)結(jié)構(gòu)與算法，原來的計(jì)算機(jī)底層方向也會繼續(xù)更新。
數(shù)據(jù)結(jié)構(gòu)與算法系列的前期以LeetCode題解為例來講解，當(dāng)?shù)竭_(dá)一定量后總結(jié)程序員必備的算法思想以及必備的數(shù)據(jù)結(jié)構(gòu)知識，這個系列的目的是讓你：看得懂、學(xué)得會、寫得出。
也歡迎大家在留言區(qū)打卡，準(zhǔn)備春招的同學(xué)可以一起刷起來。
廢話少說，開始今天的題目，這是數(shù)據(jù)結(jié)構(gòu)與算法之LeetCode刷題系列第1篇。
今天的題目是兩數(shù)之和，題目是這樣的：
給定一個整數(shù)數(shù)組與一個target，在數(shù)組中找到兩個數(shù)，其和等于target，并返回這兩個數(shù)字的下標(biāo)。
示例：
數(shù)組 nums = [2,7,11,15], target = 9，則輸出[0,1]，因?yàn)閚ums[0] + nums[1] == 9
題目不難，解決方法也有很多種，我們依次來看一下，任何題目都可以從最簡單的方法開始去想，以下代碼均為C++。
我們首先固定一個數(shù)字，比如第一個數(shù)字2，然后遍歷后面的元素，判斷是否相加等于9，有就記錄下來，沒有則看下一個數(shù)字，也就是7，最終代碼非常簡單，其時間復(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;
}
萬萬沒想到的是這樣的代碼竟然可以AC（AC是刷題的常用術(shù)語，也就是Accept，通過代碼的評測標(biāo)準(zhǔn)，包括正確性、耗時、內(nèi)存的消耗等等）。
從這里的分析我們其實(shí)可以知道，這本質(zhì)上其實(shí)是一個搜索問題，假如我知道第一個數(shù)字是2，而target是9，那么我們需要回答“這個數(shù)組中是否有7這個數(shù)字”，因此這本質(zhì)上是一個搜索問題。
既然是搜索問題，那么hash表顯然是我們最得力的武器。
關(guān)于hash表后續(xù)會有專題詳解。
依次遍歷數(shù)組中每個元素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;
}
顯然，該算法時間復(fù)雜度是O(n)，因?yàn)橐话闱闆r下可以認(rèn)為hash表能常數(shù)復(fù)雜度下查找到元素。
是不是覺得很簡單，注意，這里使用了map容器，那如果面試官要求你不得借助這種已經(jīng)寫的庫該怎么辦呢？
我們在文章開頭分析過，這其實(shí)本質(zhì)上是一個搜索問題，既然是搜索問題，那么解決該問題的另一種思路就是排序。
只要排好序剩下的就簡單了，二分查找天然就是有序搜索問題的好幫手。
因此接下來的思路就是排序加二分查找。
思路已經(jīng)介紹完畢，接下來我們手寫快排，但是我們排誰呢？
注意題目要求返回元素下標(biāo)，因此排序時需要除了數(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é)可能沒有看懂這里的排序方法，甚至認(rèn)為快排之類的排序算法只能靠死記硬背，其實(shí)不是的，這類經(jīng)典的排序算法背后都有極其重要的算法思想，比如快排背后的思想其實(shí)是divide and conquer，這是另一個龐大的話題，限于篇幅，我們會在后續(xù)專題詳解。
現(xiàn)在快排有了，接下來實(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;
}
二分查找是一個看起來極其容易但寫起來卻極其容易出錯的算法，不信你可以試試看，這里暫時還不打算詳細(xì)講解二分，后續(xù)還會多次遇到這個算法，當(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)耗時1s左右，雖然也可以AC，但可以看到運(yùn)行速度其實(shí)是很慢的，還是hash表這種解法速度最快。
可以看到，一道題目其實(shí)有很多解法，這里涉及到hash、快排與二分查找，后續(xù)我們還會多次見到這些方法，而我們在積攢足夠多的示例后會系統(tǒng)性講解這些數(shù)據(jù)結(jié)構(gòu)與算法。
聯(lián)系客服
