題目
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
思路
第一種：暴力，雙重循環(huán)羽德，時(shí)間復(fù)雜度O(n^2)
第二種：排序后，左右兩側(cè)搜索，時(shí)間復(fù)雜度O(n*log(n))
實(shí)現(xiàn)一
太久不寫c++，首先嘗試第一種熟悉一下啊胶。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0; i<nums.size(); i++){
for(int j=0; j<nums.size(); j++){
if(i==j)
continue;
if(nums[i]+nums[j]==target)
return vector<int>{i,j};
}
}
}
};
本以為會超時(shí)炮捧，但是沒想到過了=_=
不過運(yùn)行時(shí)間的排名實(shí)在難看，在后4.39%
實(shí)現(xiàn)二
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int,int>> tmp;
for(int i=0; i<nums.size(); i++){
tmp.push_back(make_pair(nums[i], i));
}
sort(tmp.begin(), tmp.end());
int i=0;
int j=tmp.size()-1;
while(tmp[i].first + tmp[j].first != target){
if(tmp[i].first + tmp[j].first > target)
j--;
else
i++;
if(i>=j){
break;
}
}
return vector<int> {tmp[i].second, tmp[j].second};
}
};
第一個(gè)考慮的問題是如何保存排序后的索引值唬血，去了解了map，但是其鍵值不能重復(fù)』秸福現(xiàn)在想想好像可以用multimap拷恨，當(dāng)時(shí)沒想到，就用了vector<pair<int,int>>再加上sort()實(shí)現(xiàn)谢肾。
第二個(gè)問題出在左右搜索上腕侄，一開始想著要從中間target/2處開始搜索，所以想了半天如何將lower_bound()用到排序好的數(shù)據(jù)上來。為此花了很多時(shí)間冕杠，甚至還嘗試了自己寫個(gè)lower_bound函數(shù)微姊，但是總是報(bào)超時(shí)，也不知道為什么拌汇。后來一想從中間開始向兩邊搜索還要考慮一些邊界問題柒桑，為什么不能從兩邊往中間搜索呢。一試就成功了噪舀，這次擊敗了82.02%的選手魁淳。
代碼比較簡單，這里就不闡述具體思路了与倡，主要是熟悉下STL的運(yùn)用界逛。
思考
看了別人的代碼，發(fā)現(xiàn)還有一種思路就是使用unordered_map加快查詢纺座，使查詢時(shí)間復(fù)雜度為O(log(n))息拜，這樣通過對每個(gè)值查找配對的值也可以達(dá)到總體O(nlog(n))的時(shí)間復(fù)雜度。但是不知道為什么他不會因?yàn)橹貜?fù)的元素而報(bào)錯(cuò)净响，難道是unordered_map支持嗎少欺，這個(gè)還有待考證。
