15.3sum.md

三数之和

题目

思路

方法一

三数之和为0, 只需从数组中取两数, 得出第三个数, 然后判断该数是否在数组中即可.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  const results = []
  const zeroNums = nums.filter(n => n === 0)
  if (zeroNums.length > 2) {
    results.push([ 0, 0, 0 ])
  }
  const length = nums.length
  for (let i = 0; i < length; i++) {
    for (let j = i + 1; j < length; j++) {
      const third = 0 - nums[i] - nums[j]
      const index = nums.findIndex(n => n === third)
      if (index !== i && index !== j && index > -1) {
        const isRepeat = results.reduce((prev, curr) => {
          if (
            curr.includes(nums[i]) &&
            curr.includes(nums[j]) &&
            curr.includes(third)
          ) {
            return true
          }
          return prev
        }, false)
        if (!isRepeat) {
          results.push([ nums[i], nums[j], third ])
        }
      }
    }
  }
  return results
};

以上的方法基本能实现功能, 缺点在于太耗时了, 利用两个指针指向的值, 推断出第三个值, 然后进行判断以及数组去重, 导致非常耗时.

方法二

1. 对数组进行排序
2. 设置第一个指针, 从左边开始, 在一次循环完之后, 指针右移一位
3. 在第一个指针的右边设置为一个新的范围, 同时在该范围最左端和最右端增加两个指针(l, r)
4. 进行while(l < r)操作, 同时进行三个指针所指的值的和判断
5. 三数之和有三种情况: >0, <0, =0.
6. 大于0时, 右指针左移
7. 小于0时, 左指针右移
8. 等于0时, 传值, 并且左右指针同时往里面移动
9. 同时对左右指针进行while循环, 判断指针与之前指针所指的值是否相等. 相等则继续移动指针.
10. 直到循环到不满足l < r

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