四数之和

https://leetcode.cn/problems/4sum/

思路

四数之和和三数之和的思路是一脉相承的，只不过三数之和是一层for循环，每次遍历一个数。四数之和可以用双层for循环。

剪枝的思路与三数之和有些不同呢，三数之和的目标值是0，而四数之和的目标值是不固定的，如果遇到负数情况会有所不同。num>target不能直接退出，如果后面加负数的话，target会变小。

• （看整体动态的过程）这个逻辑不影响right和left的变化，因为right–，sum会减小是必然，left++sum会增大也是必然。
• （看静态的遍历到num[i]的时候，左右指针还没动的时候）变化的点在于，num[i] > target,如果target是0，那么num[i]之后的数都必然大于0。 而当target<0时情况便有所不同了，num[i]>target,如果num[i+1]<0,num[i]+num[i+1]一定小于num[i]。

代码

var fourSum = function(nums, target) {
  let res = [];
  nums.sort((a,b)=>a-b);
  for(let i=0;i<nums.length-3;i++){
    //去重
    if(i>0 && nums[i]===nums[i-1]) continue;
    //剪枝
    if(num[i]>0 && num[i] > target) continue;
    for(let j=i+1;j<nums.length-2;j++){
      //去重
      if(j>i+1 && nums[j]===nums[j-1]) continue;
      //剪枝
      if(nums[i]+nums[j]>0 && nums[i]+nums[j] > target) continue;
      let left = j+1;
      let right = nums.length-1;
      while(left<right){
        let sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum > target) right--;
        if (sum < target) left++;
        if(sum === target){
          res.push([nums[i],nums[j],nums[left],nums[right]]);
          while(left<right && nums[left] === nums[left+1]) left++;
          while(left<right && nums[right] === nums[right-1]) right--;
          left++;
          right--;
        }
      }
    }
  }
  return res;
};