LeetCode 每日一题笔记

0. 前言

• 日期：2026.06.08
• 题目：15. 三数之和
• 难度：中等
• 标签：数组、双指针、排序

1. 题目理解

问题描述： 给定一个整数数组 nums，找出所有满足条件且不重复的三元组 [nums[i], nums[j], nums[k]]，要求：

• i != j, i != k, j != k
• nums[i] + nums[j] + nums[k] == 0
• 答案中不能包含重复的三元组。

示例：

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

2. 解题思路

核心观察

• 暴力三重循环复杂度为 $O(n^3)$，效率低，需要优化。
• 排序后，固定第一个数，用双指针找后两个数，复杂度降为 $O(n^2)$。
• 关键：排序+去重，避免重复三元组。

算法步骤

1. 对数组进行排序；
2. 遍历数组，固定第一个数 nums[i]；
3. 用双指针 left 和 right 分别从 i+1 和 n-1 向中间移动，寻找和为 -nums[i] 的两个数；
4. 找到符合条件的三元组后，跳过重复元素，避免重复结果；
5. 遍历结束返回所有三元组。

3. 代码实现

package lc0_lc99.lc15;

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        HashSet<List<Integer>> set = new HashSet<>();
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            int leftPos = i + 1;
            int rightPos = n - 1;
            while (leftPos < rightPos) {
                int sum = nums[i] + nums[leftPos] + nums[rightPos];
                if (sum == 0) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[leftPos]);
                    list.add(nums[rightPos]);
                    if (!set.contains(list)) {
                        set.add(list);
                        res.add(list);
                    }
                    leftPos++;
                } else if (sum > 0) {
                    rightPos--;
                } else {
                    leftPos++;
                }
            }
        }
        return res;
    }
}

4. 代码优化说明

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
    if (nums == null || nums.length == 0) {
        return new ArrayList<>();
    }

    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        // 跳过重复的第一个数，避免重复三元组
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        int target = -nums[i];
        int right = nums.length - 1;
        for (int j = i + 1; j < nums.length; j++) {
            // 跳过重复的第二个数，避免重复三元组
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }

            // 右指针向左移动，找到第一个nums[j] + nums[right] <= target的位置
            while (j < right && nums[j] + nums[right] > target) {
                right--;
            }

            // 指针相遇，无匹配结果，退出循环
            if (j == right) {
                break;
            }

            // 找到符合条件的三元组，加入结果集
            if (nums[j] + nums[right] == target) {
                res.add(Arrays.asList(nums[i], nums[j], nums[right]));
            }
        }
    }

    return res;
}
}

5. 复杂度分析

• 基础双指针+哈希去重版
  • 时间复杂度：$O(n^2)$，排序 $O(n\log n)$，双重循环 $O(n^2)$。
  • 空间复杂度：$O(n)$，哈希集合存储结果，最坏情况下所有三元组都不重复。
• 优化双指针版
  • 时间复杂度：$O(n^2)$，排序 $O(n\log n)$，双重循环 $O(n^2)$，但通过跳过重复元素减少了实际迭代次数。
  • 空间复杂度：$O(1)$，除结果集外无额外空间开销。

6. 总结

• 核心：排序+双指针，将三数之和问题转化为两数之和问题。
• 优化亮点：
  1. 跳过重复元素，避免使用哈希集合去重，降低空间开销；
  2. 提前退出条件，减少不必要的循环；
  3. 减少分支判断，代码逻辑更简洁高效。
• 关键技巧：通过排序和跳过重复元素，在保证结果不重复的同时，大幅提升算法效率。