题目

给你一个整数数组 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]]
  • 解释： 
    1
    2
    3
    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
  • -105 <= nums[i] <= 105

分析

1. 暴力解法

最直观的想法是使用三层循环，枚举所有可能的三元组 (i, j, k)，然后判断它们的和是否为 0。

  • 第一层循环 i 从 0 到 n-3
  • 第二层循环 j 从 i+1 到 n-2
  • 第三层循环 k 从 j+1 到 n-1
  • 检查 nums[i] + nums[j] + nums[k] == 0

这种方法的时间复杂度是 O(N³)，其中 N 是数组的长度。对于 N=3000 的情况，3000³ = 2.7 * 10¹⁰，这个计算量太大了，一定会超时。

此外，暴力解法还需要处理重复的三元组问题。例如，对于 [-1, 0, 1, -1, 2]，(nums[0], nums[1], nums[2]) 即 (-1, 0, 1) 和 (nums[3], nums[1], nums[2]) 即 (-1, 0, 1) 是重复的。为了去重，我们可以将找到的三元组排序后存入一个 Set 中。但这并不能解决 O(N³) 的时间复杂度问题。

因此，我们需要更高效的算法。

2. 优化思路：降维

我们可以将问题从 “三数之和” 降维到 “两数之和”。

如果我们固定了第一个数 nums[i]，那么问题就变成了：在数组剩下的部分中，寻找两个数 nums[j] 和 nums[k]，使得 nums[j] + nums[k] == -nums[i]。

这正是经典的 “两数之和” 问题。对于 “两数之和”，我们通常有两种高效的解法：

  1. 哈希表法: 遍历数组，对于每个元素 x，在哈希表中查找是否存在 target - x。时间复杂度 O(N)。
  2. 双指针法: 如果数组是有序的，可以使用头尾两个指针，根据它们的和与 target 的大小关系，向中间移动。时间复杂度 O(N)。

结合到本题，我们可以在外层循环固定 nums[i]，然后在内层使用 “两数之和” 的解法。如果我们对整个数组排序，那么使用 “双指针法” 会是最高效且最方便去重的方式。

3. 核心算法：排序 + 双指针

这成为了解决此类问题的标准范式。

算法步骤：

  1. 特判：如果数组长度小于3，直接返回空列表，因为不可能组成三元组。

  2. 排序：对整个数组 nums 进行升序排序。排序是关键，它有两个目的：

    • 方便使用双指针法快速查找。
    • 方便处理和跳过重复的元素，从而避免产生重复的三元组。

  3. 主循环（固定第一个数）: 遍历排序后的数组，用 i 作为第一个数的指针，从 0 遍历到 n-3（因为后面至少需要 left 和 right 两个数）。

    • 剪枝优化1: 如果 nums[i] > 0，由于数组已经排序，后面的数 nums[left] 和 nums[right] 也都大于0，它们的和不可能为0。因此，可以直接结束整个循环。

    • 去重处理1 (对第一个数 a): if (i > 0 && nums[i] == nums[i-1]) 这行代码是去重的关键，其目的是防止因使用重复的起始数字而产生重复的三元组。

      • 核心思想：当遇到连续相等的数字时（例如 [-1, -1, -1, 0, 1]），我们只把第一个 -1 作为三元组的起始数字 a 进行后续的双指针查找。所有跟在它后面的 -1 都会被跳过。

      • 为什么可以跳过？ :假设我们处理第一个 -1 (索引为 i) 时，已经在其后的数组部分找到了所有可能的解。当我们遇到下一个 -1 (索引为 i+1) 时，它的搜索范围是第一个 -1 搜索范围的子集。因此，任何能与第二个 -1 构成的解，必然已经被第一个 -1 找到过了。为了避免重复，我们直接跳过后续所有与 nums[i] 相等的元素。

      • i > 0 的作用：这个条件确保了 nums[i-1] 不会发生数组越界，它只在检查非首位的元素时才进行与前一个元素的比较。

  4. 双指针（寻找另外两个数）: 在主循环内部，我们初始化左指针 left = i + 1 和右指针 right = nums.length - 1。

    • 在 left < right 的条件下，进行循环。

    • 计算三数之和 sum = nums[i] + nums[left] + nums[right]。

    • 情况一：sum == 0

      • 找到了一个满足条件的三元组 [nums[i], nums[left], nums[right]]，将其加入结果列表。
      • 去重处理2 (对第二、三个数):
        • 为了避免 [[-2, 0, 2], [-2, 0, 2]] 这种情况 (假如数组中有多个0或2)，我们需要移动 left 和 right 指针，跳过所有与当前 nums[left] 和 nums[right] 相等的元素。
        • while (left < right && nums[left] == nums[left + 1]) left++;
        • while (left < right && nums[right] == nums[right - 1]) right--;
      • 在跳过重复元素后，将 left 和 right 各向中间移动一位，继续寻找下一组可能的解。left++; right--;

    • 情况二：sum < 0

      • 和太小了，需要增大。由于数组是排序的，应该将左指针 left 右移一位 (left++)，以得到一个更大的和。

    • 情况三：sum > 0

      • 和太大了，需要减小。由于数组是排序的，应该将右指针 right 左移一位 (right--)，以得到一个更小的和。

  5. 返回结果：遍历结束后，返回包含所有不重复三元组的结果列表。

复杂度分析:

  • 时间复杂度: O(N²)。其中，Arrays.sort() 的时间复杂度是 O(N log N)，主循环 O(N) 和双指针循环 O(N) 嵌套，总时间复杂度为 O(N log N + N²) = O(N²)。
  • 空间复杂度: O(log N) 或 O(N)。这取决于排序算法使用的额外空间。Java的 Arrays.sort() 对于基本数据类型使用的是快速排序的变体，其空间复杂度平均为 O(log N)，最坏情况下为 O(N)。我们返回结果的 result 列表不计入额外空间复杂度。

答案

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 创建一个列表用于存放结果
        List<List<Integer>> result = new ArrayList<>();
        
        // 1. 特判：如果数组为null或长度小于3，直接返回空列表
        if (nums == null || nums.length < 3) {
            return result;
        }
        
        // 2. 排序：对数组进行升序排序
        Arrays.sort(nums);
        
        // 3. 主循环：遍历数组，固定第一个数 nums[i]
        for (int i = 0; i < nums.length - 2; i++) {
            // 剪枝优化：如果当前数字大于0，则三数之和一定大于0，结束循环
            if (nums[i] > 0) {
                break;
            }
            
            // 去重处理 (对第一个数 a)：如果当前数字与前一个数字相同，则跳过
            // 确保 nums[i] 的值只被作为三元组的第一个元素处理一次
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // 4. 双指针：寻找另外两个数
            int left = i + 1; // 左指针，从 i 的下一位开始
            int right = nums.length - 1; // 右指针，从数组末尾开始
            
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum == 0) {
                    // 情况一：找到一个解
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    
                    // 去重处理 (对第二个数 b 和 第三个数 c)
                    // 跳过所有与当前 left 指向的元素相同的后续元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    // 跳过所有与当前 right 指向的元素相同的前续元素
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    
                    // 移动指针，寻找下一组可能的解
                    left++;
                    right--;
                } else if (sum < 0) {
                    // 情况二：和太小，需要增大，移动左指针
                    left++;
                } else { // sum > 0
                    // 情况三：和太大，需要减小，移动右指针
                    right--;
                }
            }
        }
        
        // 5. 返回结果
        return result;
    }
}