LeetCode 热题100 - 6. 三数之和（Java 题解）

LeetCode 热题100 - 6. 三数之和（Java 题解）

题目链接

https://leetcode.cn/problems/3sum/

难度

中等

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]

满足 i != j、i != k、j != k，同时满足 nums[i] + nums[j] + nums[k] == 0。

请你返回所有和为 0 且不重复的三元组。

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

解题思路

本题最优解法：排序 + 双指针，核心思路如下：

1. 先排序

   排序是去重和双指针的基础。

2. 遍历固定第一个数 nums [i]

   把问题转化为：在 i 后面找两数之和等于 -nums[i]。

3. 对 i 之后的区间使用双指针

   • left = i + 1
   • right = 数组末尾
   • 根据两数之和与目标值的大小移动指针

4. 关键：去重

   • 对 i 去重：nums[i] == nums[i-1] 跳过
   • 对 left、right 去重：找到答案后跳过重复元素

排序 + 双指针让时间复杂度从暴力 O(n3) 降到 O(n2)。

复杂度分析

• 时间复杂度：O(n2)

  排序 O(nlogn) + 遍历 O(n) + 双指针 O(n)

• 空间复杂度：O(logn) ~ O(n)

  主要是排序占用的空间

解题代码（Java）

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();int length = nums.length;// 排序：为了双指针 + 去重Arrays.sort(nums);for (int i = 0; i < length; i++) {// 对第一个数去重if (i > 0 && nums[i - 1] == nums[i]) {continue;}// 目标：两数之和 = -nums[i]int temp = -nums[i];int left = i + 1, right = length - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == temp) {// 找到一组解result.add(Arrays.asList(nums[i], nums[left], nums[right]));left++;right--;// 对 left 去重while (left < right && nums[left - 1] == nums[left]) {left++;}// 对 right 去重while (left < right && nums[right + 1] == nums[right]) {right--;}} else if (sum < temp) {// 和太小，左指针右移left++;} else {// 和太大，右指针左移right--;}}}return result;}
}

代码解释

1. 排序

   让数组有序，才能用双指针逼近目标值，同时方便去重。

2. 遍历第一个数 i

   把三数之和转为两数之和问题。

3. 去重（最关键）

   • i 重复直接跳过
   • 找到答案后，left 和 right 也要跳过重复值保证最终结果不重复。

4. 双指针逼近

   • 和偏小 → left++
   • 和偏大 → right--

示例

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

排序后：[-4,-1,-1,0,1,2]

• i=0（-4）→ 目标 4 → 无满足条件

• i=1（-1）→ 目标 1

  left=2, right=5 → -1+2=1 → 记录

  [-1,-1,2]
  

  left=3, right=4 → 0+1=1 → 记录

  [-1,0,1]
  

• i=2（-1）→ 重复，跳过

• 最终结果：[[-1,-1,2],[-1,0,1]]

易错点

1. 必须先排序，否则无法双指针 + 去重
2. 三处去重缺一不可，否则答案重复
3. 找到答案后要同时移动 left 和 right
4. 去重循环必须带上 left < right 防止越界

总结

本题是排序 + 双指针的最经典面试题，核心是转化为两数之和 + 严格去重。