解题过程：
题目要求找出不重复且和为0的元组，
如果枚举的三元组(a,b,c)满足a<=b<=c，那么就会减少(b,a,c)、(c,b,a)这样的重复；
在数组的遍历过程中，相邻两次枚举的元素不能相同，否则也会造成重复(如0,-1,1,1,1,3)。
通过上述两步可以解决重复的问题，接下来就是遍历数组，找到符合条件的a、b、c。
定义一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上，在数组中找到 abc 使得a + b +c =0，a = nums[i]、b = nums[left]、c =nums[right]
在遍历数组的过程中：
(1)如果排序后第一个元素大于0，那么后边就不会有三数之和等于0；
(2)跳过重复元素避免重复；
(3)如果三数之和大于0，说明右边界太大，right左移
(4)如果三数之和小于0，说明左边界太小，left右移
(5)如果三数之和等于0，判断判断左界和右界是否和下一位置重复，去除重复解。并同时将left、right移到下一位置，寻找新的解
class Solution {
public:
vector> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
vector> result;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) { //排序后如果第一个元素已经大于零，返回结果
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) { //去重，保证和上一次枚举的数不相同
continue;
}
int right = nums.size() - 1; //定义右指针
int target = -nums[i]; //通过-a = b + c来确定符合条件的b、c
for (int left = i + 1; left < nums.size(); left++) { //定义左指针
if (left > i + 1 && nums[left] == nums[left - 1]) { //去重复
continue;
}
while (left < right && nums[left] + nums[right] > target) { //为了满足a //指针重合，就不会有满足a+b+c=0并且b //满足 b + c = -a
result.push_back({ nums[i], nums[left], nums[right] });
}
}
}
return result;
}
};
代码随想录也提供也一种写法，原理是一样的，逻辑比较清晰，但是上边的更巧妙：
时间复杂度都是
O
(
n
2
)
O(n^2)
O(n2)。
class Solution {
public:
vector> threeSum(vector& nums) {
vector> result;
sort(nums.begin(), nums.end());
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.size(); i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
// 错误去重方法，将会漏掉-1,-1,2 这种情况
// 正确去重方法
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
if (nums[i] + nums[left] + nums[right] > 0) {
right--;
// 当前元素不合适了，可以去重
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (nums[i] + nums[left] + nums[right] < 0) {
left++;
// 不合适，去重
while (left < right && nums[left] == nums[left - 1]) left++;
} else {
result.push_back(vector{nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个三元组之后
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
return result;
}
};
题目2：18.四数之和
解法：排序+双指针
与三数之和解法类似，注意对比写法上的区别
三数之和的双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。
四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况
五数之和、六数之和等等都采用这种解法。
class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector> result;
if (nums.size() < 4) { //数组小于4直接返回结果
return result;
}
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i++) { //i从下标0开始 i为确定的第一个数，还有三个数要确定，因此要nums.size()-3
if (i > 0 && nums[i] == nums[i - 1]) { //去重
continue;
}
if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) { //确定nums[i]后，连续四数之和大于target则后面不会有符合条件的数，直接退出循环
break;
}
if ((long)nums[i] + nums[nums.size() - 3] + nums[nums.size() - 2] + nums[nums.size() - 1] < target) {
continue; //确定nums[i]后，剩下三个数无论取什么值都小于target，直接进入下一轮循环，nums[i+1]
}
for (int k = i + 1; k < nums.size() - 2; k++) { //k定义在i+1的位置
if (k > i + 1 && nums[k] == nums[k - 1]) { //去重
continue;
}
if ((long)nums[i] + nums[k] + nums[k + 1] + nums[k + 2] > target) { //确定nums[i]和nums[k]后
break; //连续四数之和大于target则剩下两个数不论取什么值不会有符合条件的数，直接退出循环
}
if ((long)nums[i] + nums[k] + nums[nums.size() - 2] + nums[nums.size() - 1] < target) { //确定nums[i]和nums[k]后
continue; //剩下两个数无论去什么值都小于target，直接进入下一轮循环，nums[j+1]
}
int left = k + 1, right = nums.size() - 1; //定义左右指针
while (left < right) { //与三数之和类似
int sum = nums[i] + nums[k] + nums[left] + nums[right];
if (sum == target) {
result.push_back({ nums[i], nums[k], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1]) { //去重
left++;
}
left++;
while (left < right && nums[right] == nums[right - 1]) { //去重
right--;
}
right--;
}
else if (sum < target) {
left++;
}
else {
right--;
}
}
}
}
return result;
}
};
同样贴上代码随想录的双指针写法：
class Solution {
public:
vector> fourSum(vector& nums, int target) {
vector> result;
sort(nums.begin(), nums.end());
for (int k = 0; k < nums.size(); k++) {
if (k > 0 && nums[k] == nums[k - 1]) { //去重
continue;
}
for (int i = k + 1; i < nums.size(); i++) {
// 正确去重方法
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (right > left) {
// nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
right--;
// 当前元素不合适了，可以去重
while (left < right && nums[right] == nums[right + 1]) right--;
// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
}
else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) {
left++;
// 不合适，去重
while (left < right && nums[left] == nums[left - 1]) left++;
}
else {
result.push_back(vector{nums[k], nums[i], nums[left], nums[right]});
// 去重逻辑应该放在找到一个四元组之后
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
// 找到答案时，双指针同时收缩
right--;
left++;
}
}
}
}
return result;
}
};
对于几数之和这种问题，并不适合使用哈希法，因为要先找到符合条件的元素放进数组中，再进行去重，这样做非常耗时
题目3：454.四数相加Ⅱ 解法：哈希表本题是使用哈希法的经典题目
解题思路：
将四个数组分为两组，Hashmap存一组nums1、nums2，另一组nums3、nums4和Hashmap进行比对。
1.首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2.遍历数组nums1、nums2，统计两个数组元素之和，和出现的次数，放到map中。
3.定义变量count，用来统计 a+b+c+d = 0 出现的次数。
4.在遍历数组nums3、nums4，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5.最后返回统计值 count
class Solution {
public:
int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
unordered_map map; //key:a+b的数值，value:a+b数值出现的次数
// 遍历数组nums1和数组nums2，统计两个数组元素之和，和出现的次数，放到map中
for (int a : nums1) {
for (int b : nums2) {
map[a + b]++; //得到所有A[i]+B[j]的值并存入哈希映射中
}
}
int count = 0; // 统计a+b+c+d = 0 出现的次数
// 在遍历数组nums3和数组nums4，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
for (int c : nums3) {
for (int d : nums4) {
if (map.find(0 - (c + d)) != map.end()) { //(a + b) - (c + d) = 0
count += map[0 - (c + d)];
}
}
}
return count;
}
};
哈希表总结
