两数之和

点击：题目链接

 解法一：暴力解法

时间复杂度：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;}
};