雖然只是一道很簡單的題，但是也給我很多思考。

剛看到這道題的時候沒有仔細思考，直接寫了個排序和二分查找，想著對每個數字查找另一個數字會不會出現，復雜度是$O(nlogn+nlogn)$，主要訓練了一下自己手寫快速排序和二分查找。

class Solution {void swap(vector<int>& a,vector<int>& b,int i,int j){int t=a[i]; a[i]=a[j]; a[j]=t;t=b[i]; b[i]=b[j]; b[j]=t;}void getPovit(vector<int>& a, vector<int>& b,int l,int r){//三者取中得到樞紐int mid = (l+r) >> 1;if(a[l] < a[mid]) swap(a, b, l, mid);if(a[r-1] < a[mid]) swap(a, b, r-1, mid);if(a[l] > a[r-1]) swap(a, b, l, r-1);}void quickSort(vector<int>& a,vector<int>& b, int l,int r){if(r-l < 2) return;int mid = (l+r) >> 1;getPovit(a, b, l, r);int povit = a[l];int i=l-1; int j=r;while(i<j){do ++i; while(a[i] < povit);do --j; while(a[j] > povit);if(i < j) swap(a, b, i, j);}quickSort(a, b, l, j+1);quickSort(a, b, j+1, r);}int bSearch(vector<int>& a, int l,int r,int x,int now){if(r<=l) return -1;int mid = (l+r) >> 1;if( a[mid] == x && mid != now) return mid;if(a[mid] < x) return bSearch(a, mid+1, r, x, now);else return bSearch(a, l, mid, x, now);}
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> b;int n = nums.size();for(int i=0; i<n; ++i){b.push_back(i);}quickSort(nums, b, 0, n);// sort(nums.begin(), nums.end());vector<int> ret;for(int i=0; i<n; ++i){int tmp = target - nums[i];int j = bSearch(nums, 0, n, tmp, i);if(-1 != j){ret.push_back(b[i]); ret.push_back(b[j]);break;}}return ret;}
};

上面的做法很傻，稍微聰明一點的做法是排序以后從兩邊開始查找。這樣的復雜度是$O(nlogn+n)$的。因為我們求的是兩個數字的和，所以對于一個排好序的數組來講，如果一個數字增大，另一個數字一定減小。因此我們用兩個指針，一個指向數組的頭部，一個指向數組的尾部，如果出現所求的和就直接返回答案，如果兩個指針和比目標小就將前一個指針后移，如果比目標大就把后一個指針前移。這種直覺很容易證明是正確的。

class Solution {void swap(vector<int>& a,vector<int>& b,int i,int j){int t=a[i]; a[i]=a[j]; a[j]=t;t=b[i]; b[i]=b[j]; b[j]=t;}void getPovit(vector<int>& a, vector<int>& b,int l,int r){//三者取中得到樞紐int mid = (l+r) >> 1;if(a[l] < a[mid]) swap(a, b, l, mid);if(a[r-1] < a[mid]) swap(a, b, r-1, mid);if(a[l] > a[r-1]) swap(a, b, l, r-1);}void quickSort(vector<int>& a,vector<int>& b, int l,int r){if(r-l < 2) return;int mid = (l+r) >> 1;getPovit(a, b, l, r);int povit = a[l];int i=l-1; int j=r;while(i<j){do ++i; while(a[i] < povit);do --j; while(a[j] > povit);if(i < j) swap(a, b, i, j);}quickSort(a, b, l, j+1);quickSort(a, b, j+1, r);}int bSearch(vector<int>& a, int l,int r,int x,int now){if(r<=l) return -1;int mid = (l+r) >> 1;if( a[mid] == x && mid != now) return mid;if(a[mid] < x) return bSearch(a, mid+1, r, x, now);else return bSearch(a, l, mid, x, now);}
public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> b;int n = nums.size();for(int i=0; i<n; ++i){b.push_back(i);}quickSort(nums, b, 0, n);// sort(nums.begin(), nums.end());int i = 0, j = n-1;while(i < j){if(nums[i] + nums[j] == target)return vector<int>{b[i], b[j]};if(nums[i] + nums[j] < target)++i;else --j; }return vector<int>();}
};

官方給出的題解是通過使用HashMap解決的，發現這樣的效率很好，然而我之前沒有接觸過HashMap，通過一番學習，用HashMap解決了一下。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashMap;unordered_map<int, int>::const_iterator it;int n = nums.size();hashMap[nums[0]] = 0;for(int i=1; i<n; ++i){it = hashMap.find(target - nums[i]);if(it != hashMap.end()){return vector<int>{it->second, i};}hashMap[nums[i]] = i;}return vector<int>();}
};

但是也沒有覺得快多少，可能是因為數據比較水看不出來差距吧。