今天的題目是兩數(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)：

vectortwoSum(vector&nums,inttarget){
vectorres;
for(inti=0;ifor(intj=i+1;jif(nums[i]+nums[j]==target){
res.push_back(i);
res.push_back(j);
}
}
}
returnres;
}

萬(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ì)有專題詳解。

依次遍歷數(shù)組中每個(gè)元素N，查找target-N是否存在于map中即可。

vectortwoSum(vector&nums,inttarget){
unordered_mapmap;
vectorres;

for(inti=0;iif(iter==map.end()){
map[nums[i]]=i;
}else{
res.push_back(i);
res.push_back(iter->second);
}
}
returnres;
}

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

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

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

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

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

排序加二分查找

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

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

voidquick_sort(vector>&nums,intb,inte){
if(b>e)return;

inti=b-1;
for(intk=b;kif(nums[k].second

intbinary_search(vector>&nums,
intb,inte,inttarget){
while(b<=?e)?{
????????int?m?=?(b?+?e)?/?2;
????????if(nums[m].second==target){
returnnums[m].first;
}elseif(nums[m].secondelse{
e=m-1;
}
}
return-1;
}

vectortwoSum(vector&nums,inttarget){
vectorres;
vector>nums_index;
intsize=nums.size();

for(inti=0;i(i,nums[i]));
}

quick_sort(nums_index,0,size-1);

for(inti=0;iif(r!=-1){
res.push_back(nums_index[i].first);
res.push_back(r);
}
}
returnres;
}