这是跟着代码随想录的顺序学习算法的第九天。

以下是学习题解时自己的一些理解与笔记，有错误欢迎指正与讨论。

18. 四数之和

参考相关链接：

18. 四数之和

代码随想录

笔记

主要思想就是在三数之和外面加了一层循环，三数之和相关的内容已经在【力扣刷题笔记】15.三数之和 中做了笔记。

值得一提的是卡哥说的 nums[i] > target 这样的剪枝是错误的。

一开始不理解，“觉得是求和，所以越加越大，排序后 nums[i] 是最小的，最小的都比 target 大了为什么不能剪枝？”

然后放到力扣里面一跑就明白了。求和并不是越加越大，因为有负数加负数的情况存在。

输入：

[1,-2,-5,-4,-3,3,3,5]
-11

输出：

预期结果：

[[-5,-4,-3,1]]

这种剪枝是错误的，这道题目target 是任意值
if (nums[i] > target) {return result;
}

/*** @param {number[]} nums* @param {number} target* @return {number[][]}*/
var fourSum = function(nums, target) {const len = nums.length;if(len < 4) return []; // 判断临界条件nums.sort((a, b) => a - b); // 排序const res = [];for(let i = 0; i < len - 3; i++) {// 这种剪枝是错误的，这道题目target 是任意值// if (nums[i] > target) {//     return result;// }// a去重if(i > 0 && nums[i] === nums[i - 1]) continue;const temp = threeSum(nums, target, i + 1)for (const k of temp) {res.push(k);}}return res;
};
var threeSum = function(nums,target,first) {const len = nums.length;const res = [];for(let i = first; i < len - 2; i++) {// a去重if(i > first && nums[i] === nums[i - 1]) continue;let l = i + 1, r = len - 1;while(l < r) {const sum = nums[first - 1] + nums[i] + nums[l] + nums[r];if(sum < target) { l++; continue };if(sum > target) { r--; continue };res.push([nums[first - 1], nums[i], nums[l], nums[r]]) // 不大于也不小于 即为等于0 存入结果// b c 去重 while(l < r && nums[l] === nums[++l]); // 短路运算while(l < r && nums[r] === nums[--r]); // 短路运算}}return res;
};