LeetCode-15-三数之和

一：题目描述：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

二：示例与提示

示例 1:

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2:

1
2
3

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3:

1
2
3

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

三：思路

暴力求解

直接暴力套三层循环，求出所有结果，或者套两个循环，用数组存下a + b的值，找 0 - (a + b)即可
- 是可以找到满足对应的结果，但是有重复结果
- 例如：[[-1,-1,2],[-1,0,1] ，[-1, 0, 1]]，重复结果不好去除，只会更加复杂

双指针

尽量在遍历中就将结果去重，不要收集完结果再去去重
想通过三个变量去控制a,b,c
先将nums数组排序，三数之和为0，有序数组更好控制范围的缩减
for循环遍历数组，i控制a元素，left指针定义在i的右边，right指针定义在数组的结尾
当i遍历到一个元素a，就通过不断左右指针，左指针右移元素b，右指针左移元素c缩减范围直到和为0
- 去重a元素：当排序过后的数组，i左边的元素等于i元素时候进行去除，不能将i 与 i右边的元素进行判断，i右边的元素是left指针指向的元素，i和left指向的元素都需要加入到结果，结果中允许出现相同元素的
- 去重b，c元素

四：代码 + 复杂度分析

双指针

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    //双指针
    const res = []
    nums.sort((a, b) =>  a - b)
    //外层遍历
    for(let i = 0; i < nums.length; i++) {
        //指针赋值
        //左指针在i右一个 右指针在末尾
        let left = i + 1
        let right = nums.length - 1
        //如果排序后 第一个数都大于0了 就直接返回了
        if(nums[i] > 0) return res
        //去重逻辑 如果左边的数等于现在的数跳过
        if(nums[i] === nums[i - 1]) continue
        //开始移动两个指针
        while(left < right) {
            let sum = nums[i] + nums[left] + nums[right]
            //和大就要缩小范围 右指针左移
            if(sum > 0) right--
            else if(sum < 0) left++
            else {
                console.log(nums[i], nums[left], nums[right])
                //收集结果
                res.push([nums[i], nums[left], nums[right]])
                //去重b 和 c，避免下次遍历到一样的三元组
                while(left < right && nums[left] === nums[left + 1]){
                    left++
                } 
                while(left < right && nums[right] === nums[right - 1]){
                    right--
                }
                //移动双指针
                left++
                right--
            }

        }
    }
    return res


};

时间复杂度：O(n log n + n^2)
- 数组排序 ,调用sort快排：O(n logn)
- 外层遍历的循环迭代了一次，其时间复杂度为 **O(n)**。
- 双指针移动遍历，O（n）线性移动
- 内部的while循环，O（n），指针最多遍历全部数组
- 总和：O（n log(n) ） + O(n ^ 2)
空间复杂度：O(n^2)
- 最坏情况下为 **O(n^2)**，因为可能有很多满足条件的三元组