目标和问题（两数&三数&四数）
LeetCode目标和问题总结
目标和，n个数和为m
https://www.jianshu.com/p/d32d3800e739
典型的dfs问题。
1.两数之和
想到的思路：
1）暴力枚举
2）排序后，双指针。分别在开头和结尾向中间遍历。
没有想到的思路：
3）hash 思路，遍历一次即可。示例代码使用的是unordered_map
遍历到x，如果target-x在hash表中出现过，返回target-x的坐标，两个坐标即为结果。如果没有出现过，则把x加入到hash表中。
相似
15.三数之和
已写博客：https://www.jianshu.com/p/7f14788ab788
题目
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
和为0且不重复。难点是不重复.
去重的难点：
- 按照顺序枚举
「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
2）对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。【在一次循环里，一个位置的元素不能重复出现两次】举个例子，如果排完序的数组为
[0, 1, 2, 2, 2, 3]
^ ^ ^
我们使用三重循环枚举到的第一个三元组为 (0, 1, 2)(0,1,2)，如果第三重循环继续枚举下一个元素，那么仍然是三元组 (0, 1, 2)(0,1,2)，产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素，即数组中的最后一个元素 33，枚举三元组 (0, 1, 3)(0,1,3)。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
//分为三层循环，因为三个数之和。
//第一层，确定一个数
//第二层，两个指针，左指针通过遍历实现，右指针每次倒着找确定的那个数。
//因为去重，所以每个位置不需要遍历第二个相同的数字，一二层循环去重，右指针因为位置元素值确定，因此不用特别写去重
可以用 双指针去改进。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//分为三层
//第一层，确定一个数
//第二层，两个指针，左指针通过遍历实现，右指针每次倒着找确定的那个数。
//因为去重，所以每个位置不需要遍历第二个相同的数字，一二层循环去重，右指针因为位置元素值确定，因此不用特别写去重
sort(nums.begin(),nums.end());
vector<vector<int>> res;
for(int i=0;i<nums.size();i++){
if(i>0 && nums[i]==nums[i-1])//第一个位置不是相同的数
continue;
int left=i+1;
int right = nums.size()-1;
int red = -nums[i];
if(left==right){
break;
}
if(nums[i]>0){
break;
}
for(;left<right;left++){
if(left>i+1&&nums[left]==nums[left-1])//第二个位置不是相同的数
continue;
while(nums[left]+nums[right]>red&&right>left)
right-=1;
if(left==right)
break;
if(nums[left]+nums[right]==red){ //相等了
vector<int> now={nums[i],nums[right],nums[left]};
res.push_back(now);
right = nums.size()-1;
// right-=1;//判断不等于之前的
continue;
}
}
}
return res;
}
};
16.最接近的三数之和
已写博客：https://www.jianshu.com/p/b35092672bf6
可以直接暴力，
无需去重，其实思路比三数之和还好想一点。
18.四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//先排序
//循环两遍，确定 三四个数
//i从0开始，下一层从i+1,然后设置j=(i+1)+1 双指针
sort(nums.begin(),nums.end());
vector<vector<int>> res;
if(nums.size()<4)
return res;
for(int i=0;i<nums.size();i++){//第一重循环
if(nums[i]>target && nums[i]>0)//开始想剪枝，但是负值+负值会更小
break;
if(i>0 && nums[i]==nums[i-1])//去重
continue;
for(int j=i+1;j<nums.size();j++){ //第二重循环
if(nums[j]>target-nums[i] && nums[j]>0)
break;
if(j>i+1 && nums[j]==nums[j-1])
continue;
int red = target-nums[i]-nums[j];
//left，right 类似快排一样遍历
int index = -1;
int left = j+1;
int right = nums.size()-1;
// cout<<left<<right<<endl;
while(left<right){
if (nums[left] + nums[right] > red) {
right--;
} else if (nums[left] + nums[right]<red) {
left++;
} else {
vector<int> tmp={nums[i], nums[j], nums[left], nums[right]};
res.push_back(tmp);
// 找到答案时，双指针同时收缩
right--;
left++;
// 去重逻辑应该放在找到一个四元组之后
while (right > left && nums[right] == nums[right + 1]) right--;
while (right > left && nums[left] == nums[left - 1]) left++;
}
}
}
}
return res;
}
};
