乐趣区

关于javascript:Leetcode18四数之和双指针法

给你一个由 n 个整数组成的数组 nums,和一个目标值 target。请你找出并返回满足下述全副条件且不反复的四元组 [nums[a], nums[b], nums, nums[d]](若两个四元组元素一一对应,则认为两个四元组反复):

0 <= a, b, c, d < n
a、b、c 和 d 互不雷同
nums[a] + nums[b] + nums + nums[d] == target
你能够按 任意程序 返回答案。
答题:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function (nums, target) {let res = []
  if (nums.length < 4) {return res}
  let len = nums.length;
  nums = nums.sort((a, b) => {return a - b})
  for (let i = 0; i < len - 1; i++) {if (i > 0 && nums[i] === nums[i - 1]) {continue}
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {return res}
    for (let j = len - 1; j > i + 2; j--) {if (nums[j] === nums[j + 1]) {continue;}

      let left = i + 1
      let right = j - 1
      while (left < right) {
        //
        let sum = nums[i] + nums[left] + nums[right] + nums[j]
        if (sum === target) {res.push([nums[i], nums[left], nums[right], nums[j]])
          while (left < right && nums[left] === nums[left + 1]) {left++}
          while (left < right && nums[right] === nums[right - 1]) {right--}
          left++
          right--
        } else if (sum < target) {left++} else {right--}
      }
    }
  }
  return res

};

四数之和跟三数之和挺类似的,都要有一个排序的过程,然而四数之和多了一个右侧边界的膨胀。
同时两头两个数字一直地尝试,找到 target 即可增加到 res 中。
向右挪动左边界的时候,首先计算一下左侧四个数字的和,如果和大于指标选项,间接输入,不必再持续前面的 for 循环了。
同时因为数字选取不能雷同,假如有一个后果第一个数抉择了 1 那么 for 循环中如果 nums[i]就不应该再有 1 呈现了。
举个例子
[2,2,1,2,2] 咱们抉择满足 target= 5 的四个数
在边界左移的过程中会呈现
[2,1,2,2] 两次但这个显著不符合要求,反复了毕竟
所以函数中要包含选项的去重
于是在第一层 for 循环第二次 for 循环以及 while 循环中都有去重操作
具体打印一下代码,体验整个过程!

退出移动版