15 三数之和（力扣：[https://leetcode.cn/problems/3sum/])
条件：给定一个含>=3个元素的数组nums，找到有多少个元素a+b+c = 0，并返回所有[a,b,c]，要求[a,b,c]不重复；
Tips：
- 题目中要求不重复，所以使用哈希还要额外去重，而由于哈希是通过映射到哈希值来记录所有可用情况的，所以使用哈希再降重效率不高；此外要求[a,b,c]中元素的下标不重复，没有要求a≠b≠c，所以注意全0和存在相等元素的数组是合法的，只是解的某一个位置上( 如a )遇到一群相同数字则只保留一个数字、其他相同不计入；
- 参考链接：由于不需要输出原下标、又要求使用的元素下标必须不同但值可以相同，所以先将数组元素根据值重新排序，再用双指针计算当前元素是否有解；而发现解后要排除相同元素，注意当前元素的重复值和边界的重复值都是只记录第一个，但当前元素的重复值是当前值和前一个元素比，重复则continue跳过本次迭代；
代码来自ai修改 ：
点击查看代码
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 定义结果集vector<vector<int>> result;// 先对数组进行排序sort(nums.begin(), nums.end());// 如果排序后是全正数数组则直接返回空resultif (nums[0] > 0) {return result;}// 存储所能走到的最大下标int size = nums.size() - 1;// 从小到大遍历数组for (int tmp = 0; tmp <= size; tmp++) {// 如果当前几个nums值重复，则跳到for的判断，前进到最后一个重复numsif (tmp > 0 && nums[tmp] == nums[tmp - 1]) {continue; // 跳过重复，只处理第一个}// 先保证当前的下标left和right没有重合for (int left = tmp + 1, right = size; left < right;) {// 比较left+right与 0 - nums[tmp]// 相等则记录left和right对应的值if (nums[tmp] + nums[left] + nums[right] == 0) {result.push_back(vector<int>{nums[tmp], nums[left], nums[right]});// 在找到一个符合条件的组后收缩边界，但前提是L+1/R-1的值不是重复的while (left < right && nums[left] == nums[left + 1])left++;while (left < right && nums[right] == nums[right - 1])right--;// 两个while循环会听到新值的前/后一位，收缩边界即可left++;right--;// L+R小则应向右移动L使L+R增大// 每次移动一位保证每次移动都会返回for进行判断当前left和right没有相遇} else if (nums[left] + nums[right] < 0 - nums[tmp]) {left++;// L+R大则应向左移动R使L+R减小} else if (nums[left] + nums[right] > 0 - nums[tmp]) {right--;}}}return result;}
};18 四数之和（力扣：[https://leetcode.cn/problems/4sum/])
条件： 给定一个数组和一个target值，要求找不重复四元组 nums[a], nums[b], nums[c], nums[d]，abcd不重复且四元组的和为target；
Tips：
- 注意，在所有去重（涉及例如nums[a+1]或者nums[b-1]）为了保证下标（的+或1操作）不越界，要把针对下标本身的约束放在前，如if( nums[a]nums[a-1] && a>0)会越界，要写成 if( a>0 && nums[a]nums[a-1]); 此外计算sum的时候要定义成long型否则也会溢出！其它见代码注释，参考链接
代码来自ai修改
点击查看代码
class Solution {public:vector<vector<int>> fourSum(vector<int>& nums, int target) {// 新建答案集vector<vector<int>> result = {};// 注意，本题和三数之和不同，最小长度为1，所以可以用nums.size排除if (nums.size() < 4) {return result;}// 不重复先排序sort(nums.begin(), nums.end());// 排序后从头挨个遍历到倒数第三个作为第一个元素nums[a]for (int a = 0; a < nums.size() - 3; a++) {// 注意，由于target值是不确定的，所以可以通过第一个nums判断// 当nums[a]大于target且为0或正数则后面不会有负数存在if (nums[a] > target && nums[a] >= 0) {break;}// 当nums[a] == nums[a+1]时只处理重复值的第一个// 但这里使用a-1为了使用continue跳过后面的重复值，注意不要让a-1越界if ( a > 0 && nums[a] == nums[a - 1] ) {continue;}// 在a去重后接着让nums[b]从nums[a]后一个开始遍历for (int b = a + 1; b < nums.size() - 2; b++) {// 去重，原理同aif ( b > a+1 && nums[b] == nums[b - 1] ) {continue;}// 在确定ab后，一头一尾开始收缩c、d的范围直到cd相遇for (int c = b + 1, d = nums.size() - 1; c < d;) {// 出现答案元组if ((long)nums[a] + nums[b] + nums[c] + nums[d] == target) {result.push_back(vector<int>{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--;// 当前答案小于target, 向右收缩边界使增大} else if ((long)nums[a] + nums[b] + nums[c] + nums[d] < target) {c++;}// 当前答案大于target, 向左收缩边界使减小else if ((long)nums[a] + nums[b] + nums[c] + nums[d] > target) {d--;}}}}return result;}
};