JS_LeetCode06：三数之和

image-20250513224811928

6.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

排序

这道题呢，首先三个数的求和为0，将问题简化为遍历每个数num，找到另外两个数的求和等于num的相反数。

找两个数，因此可以利用双指针，但是双指针移动的策略怎么决定呢？没有头绪呀！

因此！考虑到数的大小关系！可以先对数组进行排序！（反正题目没有要求顺序，只要求找到这三个数）

而且！题目要求三元组不要重复，排序之后相同的数字会连成一片，更容易跳过它们！

排序的方法是对数组使用sort，注意加条件nums.sort((a,b)=>a-b)，不加条件排序的话是按照unicode字符编码顺序进行排序的（适用于字符串，不适用于数字！默认是把数字转为字符串后按字典顺序排序，比如10、2、5）

所以我们要传入比较函数！

1
nums.sort((a, b) => a - b); //从小到大
1
nums.sort((a, b) => b - a); //从大到小

最重要的是排序和去重，在移动指针的时候判断是不是重复了，要跳过。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  let res = []  
  let nums_ = nums.sort((a, b) => a - b)
  for (let i=0;i<nums_.length;i++){
    if(i>0 && nums_[i]===nums_[i-1]) continue
    let left = i+1
    let right = nums_.length-1
    const target = 0 - nums_[i]
    while (left < right){
        if(nums_[left]+nums_[right]==target){
            res.push([nums_[i],nums_[left],nums_[right]])
            while(nums_[left]===nums_[left+1]&&left<right){
                left ++
            }
            while(nums_[right]===nums_[right-1]&&left<right){
                right --
            }
            left ++
            right --
        }else if(nums_[left]+nums_[right] > target){
            while(nums_[right]===nums_[right-1]&&left<right){right --}
            right--
        }else if(nums_[left]+nums_[right] < target){
            while(nums_[left]===nums_[left+1]&&left<right){left ++}
            left ++
        }
    }
  }
  return res
};