starry
Search K

Appearance

三数之和 ​

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

思路分析 ​

问题理解 ​

这道题有两个核心难点：

  1. 找到所有和为 0 的三元组 - 如何高效地搜索
  2. 结果不能重复 - 如何避免重复的三元组

暴力解法的问题 ​

最直观的想法是三重循环枚举 i, j, k：

时间复杂度：O(n³)
还需要额外用 Set 去重，非常低效

排序 + 双指针思路 ​

核心思想：先排序，然后固定一个数 nums[i]，在剩余区间用双指针找另外两个数。

为什么排序后可以用双指针？

  • 排序后数组有序，双指针可以根据当前和的大小决定移动方向
  • sum > 0：说明右边的数太大，右指针左移
  • sum < 0：说明左边的数太小，左指针右移
  • sum == 0：找到一个答案

算法流程 ​

  1. 排序：将数组升序排列
  2. 遍历固定第一个数：i 从 0 到 n-3
  3. 剪枝优化：
    • 如果 nums[i] > 0，后面的数都是正数，不可能和为 0，直接退出
    • 如果 nums[i] == nums[i-1]，跳过重复元素，避免重复解
  4. 双指针搜索：j = i+1，k = n-1
    • 计算 sum = nums[i] + nums[j] + nums[k]
    • 根据 sum 调整 j 或 k
    • 找到答案后，跳过重复的 nums[j] 和 nums[k]

去重技巧 ​

本题去重是关键，需要在三个位置去重：

  1. 第一个数 i：if (i > 0 && nums[i] == nums[i-1]) continue
  2. 第二个数 j：找到答案后 while (j < k && nums[j+1] == nums[j]) j++
  3. 第三个数 k：找到答案后 while (j < k && nums[k-1] == nums[k]) k--

复杂度分析 ​

  • 时间复杂度：O(n²)，排序 O(nlogn) + 双重循环 O(n²)
  • 空间复杂度：O(logn)，排序所需栈空间（不计结果数组）

代码实现 ​

java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 15. 三数之和
 * <a href="https://leetcode.cn/problems/3sum/submissions/688796493/">...</a>
 */
public class P15threeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] > 0) {
                break;
            }
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum > 0) {
                    k--;
                } else if (sum < 0) {
                    j++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j < k && nums[j + 1] == nums[j]) {
                        j++;
                    }
                    j++;
                    while (j < k && nums[k - 1] == nums[k]) {
                        k--;
                    }
                    k--;
                }
            }
        }

        return res;
    }
}