LeetCode 15 三数之和

15. 三数之和

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

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

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解法1

思路: 三层循环暴力解,然后再去重

结果: O(n^3)自然好不到那里去,并且,去重也不容易啊

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let res = [];
    for(let i = 0; i < nums.length; ++ i) {
        for(let j = i + 1; j < nums.length - 1; ++j) {
            for(let k = j + 1; k < nums.length -1 ; ++ k) {
                if(nums[i] + nums[j] + nums[k] == 0) {
                    res.push([nums[i],nums[j],nums[k]]  )
                }
            }
        }
    }
    return res
};

解法2

思路: 双指针法

先把给定的nums排序,复杂度为O(NlogN)
固定3个指针中最左(最小)数字的指针k,双指针i,j分别设在数组索引(k,len(nums))两端,通过双指针交替向中间移动,记录对于每个固定指针k所满足的nums[k] + nums[i] + nums[j] == 0的i, j组合:
1. 当nums[k] > 0的时候直接break跳出,因为nums[j] >= nums[i] >= nums[k] > 0,即nums[k] > 0的时候三个数字都会 > 0,此时固定指针k之后不会再有结果了
2. 当 k > 0并且 nums[k] == nums[k - 1]时就跳过此元素nums[k]: 因为已经将nums[k - 1]的所有组合加入到结果中,本次双指针搜索只会得到重复的组合
3. i, j 分别设在数组索引(k, len(nums)) 两端, 当 i < j 时循环计算 s = nums[k] + nums[i] + nums[j] , 并按照以下规则进行双指针移动:
  - 当 s < 0 时, i += 1 并跳过所有重复的 nums[i]
  - 当 s > 0 时, j -= 1 并跳过所有重复的 nums[j]
  - 当 s == 0 时, 记录组合 [k, i, j] 到 res, 执行 i += 1 和 j -= 1 并跳过所有重复的 nums[i] 和 nums[j], 防止记录到重复组合

结果:

时间复杂度 O(n^2): 其中固定指针k循环复杂度 O(N)O(N)，双指针 i，j 复杂度 O(N)O(N)。
空间复杂度O(1)：指针使用常数大小的额外空间。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    nums.sort((a,b) => a-b)
    let res = []
    for(let k = 0; k < nums.length - 2;  ++ k) {
        // 最小的都大于0了,就没必要再往下了
        if(nums[k] > 0) break
        if(k > 0 && nums[k] == nums[k - 1]) continue
        let i = k +1, j = nums.length -1
        while( i < j) {
            s = nums[k] + nums[i] + nums[j]
            if(s < 0) {
                while(i < j && nums[i] == nums[++i]);
            } else if (s > 0){
                while(i < j && nums[j] == nums[--j]);
            } else {
                res.push([nums[k], nums[i], nums[j]])
                while(i < j && nums[i] == nums[++i]);
                while(i < j && nums[j] == nums[--j]);
            }
        }
    }
    return res
};

》双指针很棒搞熟悉了得