兩數之和

點擊：題目鏈接

?解法一：暴力解法

時間復雜度：O(N^2)

算法思路：兩層for循環即可列出所有兩個數字的組合，判斷是否等于目標值

算法流程：

兩層 for 循環： 外層 for 循環依次枚舉第?個數 a ；

內層 for 循環依次枚舉第?個數 b ，讓它與 a 匹配；

ps ：這?有個魔?細節：我們挑選第?個數的時候，可以不從第?個數開始選，因為 a 前 ?的數我們都已經在之前考慮過了；因此，我們可以從 a 往后的數開始列舉。

然后將挑選的兩個數相加，判斷是否符合?標值。

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n = price.size();for(int a = 0;a<n;a++){for(int b = 1;b<n;b++){if(price[a]+price[b]==target){return {price[a],price[b]};}}}return{-1,-1};}
};

會超時

解法二：雙指針?

時間復雜度：O(N)

算法思路： 注意到本題是升序的數組，因此可以?「對撞指針」優化時間復雜度。

算法流程（附帶算法分析，為什么可以使?對撞指針）：

a. 初始化 left，right 分別指向數組的左右兩端（這里不是我們理解的指針，而是數組的下標）

b. 當 left < right 的時候，一直循環。
i. 當 nums [left] + nums [right] == target 時，說明找到結果，記錄結果，并且返回；
ii. 當 nums [left] + nums [right] < target 時：

• 對于 nums [left] 而言，此時 nums [right] 相當于 nums [left] 能碰到的最大值（別忘了，這里是升序數組哈～）。如果此時不符合要求，說明在這個數組里面，沒有別的數符合 nums [left] 的要求了（最大的數都滿足不了你，你已經沒救了）。因此，我們可以大膽舍去這個數，讓 left++，去比較下一組數據；
• 那對于 nums [right] 而言，由于此時兩數之和是小于目標值的，nums [right] 還可以選擇比 nums [left] 大的值繼續努力達到目標值，因此 right 指針我們按兵不動；
  iii. 當 nums [left] + nums [right] > target 時，同理我們可以舍去 nums [right]（最小的數都滿足不了你，你也沒救了）。讓 right--，繼續比較下一組數據，而 left 指針不變（因為他還是可以去匹配 nums [right] 更小的數的）。

代碼：

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0,right = price.size()-1;while(left<right){if(price[left]+price[right]>target){right--;}    else if(price[left]+price[right]<target){left++;}else{return {price[left],price[right]};}}return{-1,-1};}
};

三數之和

點擊：題目鏈接

算法思路：

本題與兩數之和類似，是非常經典的面試題。

與兩數之和稍微不同的是，題目中要求找到所有 “不重復” 的三元組。那我們可以利用在兩數之和那里用的雙指針思想，來對我們的暴力枚舉做優化：
i. 先排序；
ii. 然后固定一個數 a：
iii. 在這個數后面的區間內，使用 “雙指針算法” 快速找到兩個數之和等于 -a 即可。

但是要注意的是，這道題里面需要有 “去重” 操作～
i. 找到一個結果之后，left 和 right 指針要 “跳過重復” 的元素；
ii. 當使用完一次雙指針算法之后，固定的 a 也要 “跳過重復” 的元素。

這里算法思想不難，需要注意一些極端情況的處理，比如{0，0，0}，這里需要處理好你的邊界。

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//先排序sort(nums.begin(),nums.end());//返回的是一個二維vector<vector<int>> vt;int i = 0,left = 1,right = nums.size()-1;//雙指針for(i = 0;i<nums.size()-2;i++)//固定數a{if(nums[i]>0){break;//小優化}left = i+1;right = nums.size()-1;while(left<right){if(nums[left]+nums[right]>-nums[i]){right--;}else if(nums[left]+nums[right]<-nums[i]){left++;}else if(nums[left]+nums[right]==-nums[i]){vt.push_back({ nums[i],nums[left],nums[right] });//去重//考慮相同數字，只能單邊跳，不要兩邊一起跳，否則會少算一些組合//注意left+1可能越界while(left<right&&nums[left]==nums[left+1]){left++;}//right-1同理while(left<right&&nums[right]==nums[right-1]){right--;}left++;right--;}}//i+1也可能越界while(i<nums.size()-2&&nums[i+1]==nums[i]){i++;}}return vt;}
};

四數之和

點擊：題目鏈接

算法思路:?和上題基本一樣，不過這道題可能會有一點小坑，這里出現了4個數相加會大于INT_MAX的情況，所以需要處理一下，去重操作基本可上題一樣。

a.依次固定?個數 a ；

b.在這個數 a 的后?區間上，利?「三數之和」找到三個數，使這三個數的和等于 target - a 即可。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> vt;int a,b,c,d;for(a=0;a<nums.size();a++){if(nums.size()<3){break;}for(b = a+1;b<nums.size()-2;b++){c = b+1;d = nums.size()-1;while(c<d){long max = (long)nums[c]+nums[d];if(nums[a]+nums[b]==target-max){vt.push_back({nums[a],nums[b],nums[c],nums[d]});while(c<d&&nums[c]==nums[c+1]){c++;}while(c<d&&nums[d]==nums[d-1]){d--;}c++;d--;}else if(nums[a]+nums[b]<target-max){c++;}else{d--;}}while(b<nums.size()-2&&nums[b]==nums[b+1]){b++;}}while(a<nums.size()-3&&nums[a]==nums[a+1]){a++;}}return vt;}
};