LeetCode LCR 007. 三数之和 (Java)

题目描述

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

解题思路

核心方法：排序 + 双指针

1. 排序：首先将数组排序，便于后续去重和双指针操作。
2. 固定第一个数：遍历数组，固定第一个数 a。
3. 双指针找剩余两数：对于固定的 a，使用左指针 left（初始指向 a 的下一个元素）和右指针 right（初始指向数组末尾），寻找满足 a + b + c = 0 的 b 和 c。
4. 去重：在遍历过程中，跳过重复元素以避免重复的三元组。

关键步骤详解

1. 排序的作用

排序后，相同的元素会相邻，便于后续跳过重复元素。例如，输入 [-1,0,1,2,-1,-4] 排序后为 [-4,-1,-1,0,1,2]，相邻的 -1 可以方便地通过条件判断跳过。

2. 固定第一个数 a

遍历数组时，固定 a = nums[i]。若 a > 0，由于数组已排序，后面的数均为正数，无法满足三数之和为0，直接终止循环。

3. 双指针寻找 b 和 c

• 双指针初始化：left = i + 1，right = nums.length - 1。
• 调整指针：
  • 若 a + nums[left] + nums[right] < 0：需要增大总和，左指针右移。
  • 若 a + nums[left] + nums[right] > 0：需要减小总和，右指针左移。
  • 若等于0：记录结果，并移动指针跳过重复元素。

4. 去重逻辑

• 对 a 去重：若当前 nums[i] 与前一个数相同（i > 0 且 nums[i] == nums[i-1]），跳过以避免重复。
• 对 b 和 c 去重：找到有效三元组后，跳过所有与当前 left 和 right 相同的元素。

代码实现

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) break; // 提前终止
        if (i > 0 && nums[i] == nums[i-1]) continue; // 对a去重
        
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 对b和c去重
                while (left < right && nums[left] == nums[left+1]) left++;
                while (left < right && nums[right] == nums[right-1]) right--;
                left++;
                right--;
            }
        }
    }
    return result;
}

力扣通过截图

复杂度分析

• 时间复杂度：O(n²)。排序 O(n log n)，外层循环 O(n)，内层双指针 O(n)，总体 O(n²)。
• 空间复杂度：O(1)。忽略结果存储空间，仅用常量空间。

示例解析

以输入 nums = [-1,0,1,2,-1,-4] 为例：

1. 排序后数组：[-4, -1, -1, 0, 1, 2]。
2. 固定 a = -4：双指针范围为 [-1, 2]，无法找到和为4的组合。
3. 固定 a = -1（第一个 -1）：
   • left 指向第二个 -1，right 指向 2，和为0，记录 [-1, -1, 2]。
   • 调整指针跳过重复元素，继续找到 [-1, 0, 1]。
4. 后续元素去重：跳过重复的 a，最终得到结果。

总结

通过排序预处理，结合双指针高效寻找两数之和，同时在每一步跳过重复元素，确保结果唯一。这种方法巧妙地将时间复杂度降至 O(n²)，是解决此类问题的经典思路。