18.4sum.md

四数之和

题目

思路

该题类似三数之和. 排序后, 设置双指针, 确定一个范围, 然后设置两个指针(l,r), 而后与三数之和一样的操作, 即可得到值

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
  nums.sort((a, b) => a - b)
  const results = []
  const { length } = nums
  for (let i = 0; i < length - 3; i++) {
    if (i === 0 || nums[i] !== nums[i - 1]) {
      for (let j = i + 1; j < length - 2; j++) {
        if (j === i + 1 || nums[j] !== nums[j - 1]) {
          let l = j + 1
          let r = length - 1
          while (l < r) {
            const result = nums[i] + nums[j] + nums[l] + nums[r] - target
            if (result === 0) {
              results.push([nums[i], nums[j], nums[l], nums[r]])
              while (l < r && nums[l] === nums[l + 1]) {
                l++
              }
              while (l < r && nums[r] === nums[r - 1]) {
                r--
              }
              l++
              r--
            } else if (result > 0) {
              r--
            } else {
              l++
            }
          }
        }
      }
    }
  }
  return results
};