15-三数之和

Doublew2w大约 4 分钟

给你一个整数数组 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：

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

示例 3：

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

提示：

3 <= nums.length <= 3000
-10 ⁵ <= nums [i] <= 10 ⁵

前置知识

双指针

思路：排序+双指针

如果使用「暴力枚举」的方式，时间复杂度为 $O(n^3)$ , 最后还要通过哈希表进行去重。

为了「不重复」，我们先要排序。这样就能保证我们每一层循环都可以过滤掉相同的元素，而且能快速做出剪枝

排序的时间复杂度为 $O(nlogn)$

在固定两个元素的情况下，第三个元素会导致和为 <0 >0 =0。而两个元素的交替移动也能达到这个效果。

定义三个指针 k, i, j，其中 k 指向最左的元素，双指针 i, j 分别在数组索引（k, length(nums)）处, 双指针 i , j 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums [k] + nums [i] + nums [j] == 0 的 i, j 组合：

如果 nums[k] > 0 ，而 nums[k] 又是最小，所以和肯定 > 0，终止循环
如果 nums[k] == nums[k-1] 有可能是重复答案，处理一次即可
双指针 i, j 变动情况：
- 如果和 < 0, 说明 i 需要往右边移动，移动的时候要注意处理相同元素情况
- 如果和 > 0, 说明 j 需要往左边移动，移动的时候要注意处理相同元素情况
- 如果和 = 0, i 和 j 同时往中间移动的时候处理相同元素的情况

关键点

为了 “不可以包含重复的三元组”，通过排序容易找到相同的三元组答案。
为了更有效的找到有效解，双指针「交替向中间移动」

代码

语言支持：Java

Java Code:


class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 三重循环枚举，不重复则需要
        // 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
        // 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素；
        // 因此需要先排序。
        // 双指针为什么要交替移动，往中间靠拢
        // 在固定两重循环元素的情况，第三个元素导致的三数之和有可能导致 > 0 ,= 0 < 0，也有可能 = 0（重复答案）
        // 而 < 0 时，第二个枚举元素的下标要右边移动，增大总和
        // 而 > 0 时，只能让第三个枚举元素的下标向左移动，减小总和
        // = 0，就是当前答案，随后继续交替移动，排除重复答案、
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length <3){
            return res;
        }
        Arrays.sort(nums);
        for(int k = 0;k < nums.length; k++){
            if(nums[k] > 0) break; // 此时剩余两个元素都 > 0，往后的查找不满足。
            if(k > 0 && nums[k] == nums[k - 1]) continue; // 找到重复答案（题目要求不重复）
            int i = k + 1,j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]); // 不判断相同元素
                }else if(sum > 0){
                    while(i < j && nums[j] == nums[--j]); // 不判断相同元素
                }else if(sum == 0){
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k],nums[i],nums[j])));
                    while(i < j && nums[i] == nums[++i]); // 不判断相同答案的元素
                    while(i < j && nums[j] == nums[--j]); // 不判断相同答案的元素
                }
            }
        }
        return res;

    }
}

复杂度分析

令 n 为数组长度。

时间复杂度： $O(n^2)$ ，排序的时间复杂度为 $O(nlogn)$ 。双重循环的时间复杂度为 $O(n^2)$
空间复杂度： $O(1)$ ，指针使用常数大小的额外空间，忽略答案的存储空间。

15-三数之和

题目地址(15. 三数之和 - 力扣（LeetCode）)

题目描述

前置知识

思路：排序+双指针

关键点

代码