题目名称

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例

输入：nums = [-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

题解

这道题有几个点需要注意一下

  • 最后返回的数据是去重后的数组，也就是说按照从小到大排列后，没有包含同样序列的子元素，数组去重同样是一个难点
  • 注意执行时间，如果强行去循环的话，因为复杂度是 O(n^3),所以最后一定是会超时的

数组去重的话可以采用 Set 来存储得到的数组，不过需要把数组排序之后，转成字符串存放

循环的采用双指针的方式

在最开始先把原数组按照从小到大排列，这样我们就不必再对得到的结果进行排序操作，而且再循环时还可以排除第一个元素大于0的循环，

接下来采用双指针的方式，从数组的两端进行和的对比，因为第一个数的大小已经固定，所以只需要确保剩余两个数加上第一个数的和为0就可以了，如果和小于0，说明负数过大，所以左指针右移,如果和大于0，说明正数过大，所以右指针左移

最后将得到的结果数组转化成能够识别的内容

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var threeSum = function(nums) {
    let sum = [], hash = new Set();
    if(nums.length < 3) return sum
    nums = nums.sort((a, b) => a - b)
    for(let i = 0; i < nums.length - 2; i++) {
        let first = nums[i]
        if(first > 0) break;
        let l = i + 1, r = nums.length - 1
        while(l < r) {
            let second = nums[l], third = nums[r]
            let s = first + second + third
            if(s < 0){ l++; continue;}// 和小于0，说明负数过大，所以左指针右移，减少
            if(s > 0){ r--; continue;}// 和大于0，说明正数过大，所以右指针左移，减少
            hash.add(`${first},${second},${third}`)
            l++;
            r--;

        }
    }
    return Array.from(hash).map(item => item.split(",").map(item => +item))
};