Leetcode 15.三数之和

一道非常经典的题目，力扣链接15. 三数之和 - 力扣（LeetCode）

思路详解

首先看题目，因为不限制三元组的顺序，所以我们可以先排序，按照从小到大排序。

首先假设我们设三个点为i,j,k,首先假设第一个数nums[i]已经定死，此时问题被化解为在[i+1,n-1]的区间范围内找到和为-nums[i]的数，那么这道题是不是就成了经典题目1. 两数之和 ，

但是相比两数之和多了两个限制条件

1. 我们需要找到区间范围内和为-nums[i]的两个数的个数
2. 这两个数不能重复

那么如何在这个有序数组中找到两个数呢？

这个时候就要提到双指针，设左指针为l，右指针为r

如果nums[l]+nums[r] > -nums[i]这证明三数之和偏大，需要把大的数变小，则需要将右指针r向左移，

反之nums[l]+nums[r] < -nums[i]这证明三数之和偏小，需要把小的数变大，则需要把左指针l向右移，

而如果nums[l]+nums[r] == -nums[i]则需要将答案记录，并且将左指针右指针同时移动

现在我们解决了第一个问题，那么第二个问题如何解决呢？

举个例子，现在有一个区间为[-1,-1,1,1]此时索引0和3配对了，那么同时移动之后，1和2也会配对

这就需要我们保证，在移动的过程中，指针移动后的值不能和移动之前的值相等，即如果移动指针后的值和上一次的值相等，则继续移动。

一句话就是

while(nums[l]==nums[l-1]){l++}//左指针移动，并保证nums[l]!=nums[l-1]
while(nums[r]==nums[r+1]){r--}//右指针移动，并保证nums[r]!=nums[r+1]

现在两个数的去重实现了，三个数怎么办？例如[-1,-1,0,0,1,1]

其实同样，我们只要保证最左边的i也不相等即可，代码就是

for (let i = 0 ; i < n - 2 ; i++){
    if (i != 0 && nums[i] == nums[i-1]){continue}
    //下面继续处理
    //...
}

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const ans = []
  const n = nums.length
  let i = 0
  //先排序
  nums.sort((a, b) => {
    return a - b
  })

  const getSum = (i, l, r) => {
    return nums[i] + nums[l] + nums[r]
  }

  const twoPoint = (l, r) => {
    const rMove = () => {
      r--
      while ((nums[r] == nums[r + 1]) && l < r) {
        r--
      }
    }
    const lMove = () => {
      l++
      while ((nums[l] == nums[l - 1]) && l < r) {
        l++
      }
    }
    while (l < r) {
      const sum = getSum(i, l, r)
      if (sum > 0) {//大于0表示右指针偏右
        rMove()
      } else if (sum < 0) {//小于0左指针偏左
        lMove()
      } else {
        ans.push([nums[i], nums[l], nums[r]])
        rMove()
        lMove()
      }

    }
  }

  //最外层循环，最左边的指针
  for (i = 0; i < n - 2; i++) {
    //保证左边去重
    if (i != 0 && nums[i] === nums[i - 1]) {
      continue
    }
    //双指针
    twoPoint(i + 1, n - 1)
  }
  return ans
};

代码优化

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  const ans = []
  const n = nums.length
  let i = 0
  //先排序
  nums.sort((a, b) => {
    return a - b
  })

  const getSum = (i, l, r) => {
    return nums[i] + nums[l] + nums[r]
  }

  const twoPoint = (l, r) => {

    const rMove = () => {
      r--
      while ((nums[r] == nums[r + 1]) && l < r) {
        r--
      }
    }
    const lMove = () => {
      l++
      while ((nums[l] == nums[l - 1]) && l < r) {
        l++
      }
    }
    while (l < r) {
      const sum = getSum(i, l, r)
      if (sum > 0) {//大于0表示右指针偏右
        rMove()
      } else if (sum < 0) {//小于0左指针偏左
        lMove()
      } else {
        ans.push([nums[i], nums[l], nums[r]])
        rMove()
        lMove()
      }

    }
  }

  //最外层循环，最左边的指针
  for (i = 0; i < n - 2; i++) {
    //保证左边去重
    while (i != 0 && nums[i] === nums[i - 1]) {
      i++
    }
    //最小的已经不行
    if (nums[i]+nums[i+1]+nums[i+2]>0){
      break      
    }
    //最大的还行吗
    if(nums[i]+nums[n-1]+nums[n-2]<0){
      continue
    }
    //双指针
    twoPoint(i + 1, n - 1)
  }
  return ans
};

Q.E.D.