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²)，是解决此类问题的经典思路。