LeetCode Hot 100 - 15. 三数之和（双指针经典题）

难度中等 | 面试频率⭐⭐⭐⭐⭐题目描述给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! knums[i] nums[j] nums[k] 0请你返回所有和为0且不重复的三元组。注意答案中不可以包含重复的三元组。示例示例 1text输入nums [-1,0,1,2,-1,-4] 输出[[-1,-1,2],[-1,0,1]] 解释 nums[0] nums[1] nums[2] (-1) 0 1 0 nums[1] nums[2] nums[4] 0 1 (-1) 0 nums[0] nums[3] nums[4] (-1) 2 (-1) 0 不同的三元组是 [-1,0,1] 和 [-1,-1,2]示例 2text输入nums [0,1,1] 输出[] 解释唯一可能的三元组和不为 0示例 3text输入nums [0,0,0] 输出[[0,0,0]]提示3 nums.length 3000-10^5 nums[i] 10^5解题思路核心思想三数之和 → 两数之和 → 双指针将问题分解固定一个数nums[i]在剩余数组中寻找两个数使其和为-nums[i]使用双指针法高效寻找为什么排序排序的作用✅ 可以高效跳过重复元素✅ 双指针可以正确地向中间移动✅ 当nums[i] 0时后续不可能有解因为都已排序且 ≥ nums[i]完整代码javaclass Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); // 边界条件长度不足 3 直接返回 if (nums.length 3) { return res; } // 排序升序 Arrays.sort(nums); // 固定第一个数 for (int i 0; i nums.length - 2; i) { // 剪枝优化如果当前数 0后面都大于 0三数和不可能为 0 if (nums[i] 0) { break; } // 跳过重复的第一个数 if (i 0 nums[i] nums[i - 1]) { continue; } int left i 1; int right nums.length - 1; // 双指针寻找两数之和为 -nums[i] while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { // 找到一组解 res.add(Arrays.asList(nums[i], nums[left], nums[right])); // 跳过重复的 left 值 while (left right nums[left] nums[left 1]) { left; } // 跳过重复的 right 值 while (left right nums[right] nums[right - 1]) { right--; } // 移动指针到新的位置 left; right--; } else if (sum 0) { // 和太小需要增大移动左指针 left; } else { // 和太大需要减小移动右指针 right--; } } } return res; } }代码详解1. 排序预处理javaArrays.sort(nums);排序后数组变为有序便于双指针和去重。2. 固定第一个数javafor (int i 0; i nums.length - 2; i)只需遍历到倒数第三个元素因为至少需要 left 和 right 两个位置。3. 剪枝优化javaif (nums[i] 0) break;因为数组已排序如果nums[i] 0后面所有数都 ≥ nums[i] 0三数和不可能为 0。4. 跳过重复的第一个数javaif (i 0 nums[i] nums[i - 1]) continue;避免产生重复的三元组。5. 双指针寻找两数之和javaint left i 1; int right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; // 根据 sum 与 0 的大小关系移动指针 }6. 跳过重复元素找到解后跳过所有相同的nums[left]和nums[right]javawhile (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--;复杂度分析操作时间复杂度空间复杂度排序O(n log n)O(log n)快排栈空间外层循环O(n)-内层双指针O(n)每个 i-总计O(n²)O(log n)到 O(n)时间复杂度O(n²)排序 O(n log n) 是次要项空间复杂度O(log n) ~ O(n)取决于排序实现测试验证javapublic static void main(String[] args) { Solution solution new Solution(); // 示例 1 int[] nums1 {-1, 0, 1, 2, -1, -4}; System.out.println(solution.threeSum(nums1)); // 输出: [[-1, -1, 2], [-1, 0, 1]] // 示例 2 int[] nums2 {0, 1, 1}; System.out.println(solution.threeSum(nums2)); // 输出: [] // 示例 3 int[] nums3 {0, 0, 0}; System.out.println(solution.threeSum(nums3)); // 输出: [[0, 0, 0]] // 边界测试 int[] nums4 {-2, 0, 0, 2, 2}; System.out.println(solution.threeSum(nums4)); // 输出: [[-2, 0, 2]] }️ 图解示例以nums [-1, 0, 1, 2, -1, -4]为例排序后[-4, -1, -1, 0, 1, 2]texti0, nums[i]-4 left1(-1), right5(2), sum-3 → 太小left i1, nums[i]-1跳过 i2 重复 left3(0), right5(2), sum1 → 太大right-- left3(0), right4(1), sum0 → 找到 [-1,0,1] left4(1), right3 退出 i3, nums[i]0 left4(1), right5(2), sum3 → 太大right-- left4(1), right4 退出 i4, nums[i]1 0 → break 关键点总结要点说明核心思想三数之和 → 两数之和双指针必要步骤先排序剪枝优化nums[i] 0直接 break去重策略跳过所有重复的nums[i]、nums[left]、nums[right]时间复杂度O(n²)空间复杂度O(1)不计返回结果⚠️ 常见错误忘记排序没有排序无法使用双指针去重不完整只对第一个数去重忘记对 left/right 去重边界错误left right写成left right剪枝遗漏nums[i] 0时忘记 break 举一反三变形题题目解法要点1. 两数之和哈希表 O(n)16. 最接近的三数之和双指针 记录最接近值18. 四数之和在三数之和基础上再套一层循环454. 四数相加 II分组 哈希表 面试技巧面试官可能会问Q为什么不能用哈希表直接做A可以但需要 O(n²) 存储两数之和且去重更复杂双指针更优。Q如果要求返回下标而不是值A不能排序需要用哈希表存储所有两数之和及对应下标组合。Q如何扩展到 k 数之和A外层固定 k-2 个数最内层使用双指针时间复杂度 O(n^(k-1))。 相关链接LeetCode 原题15. 三数之和题解参考官方题解 欢迎在评论区讨论交流如果这篇文章对你有帮助请点赞支持 关注我持续更新 LeetCode Hot 100 题解Happy Coding!