AlgoViz Lab交互式算法学习Algorithms first
三数之和 · 交互式算法学习
找出所有和为 0 且不重复的三元组。
#15 · 双指针
三数之和
3Sum
nums = [-1,0,1,2,-1,-4]线性序列4 个关键状态
步骤 1排序后固定 -4，左右和仍太小。
sum=-3-4
0-1
1-1
20
31
42
5推荐
排序 + 双指针
时间
O(n²)空间 O(1) 除答案排序后固定第一个数，用左右指针寻找相反数，并跳过重复值。
1function threeSum(a) {2 a.sort((x, y) => x - y);3 const out = [];4 for (let i = 0; i < a.length - 2; i++) {5 if (i && a[i] === a[i - 1]) continue;6 let l = i + 1,7 r = a.length - 1;8 while (l < r) {9 const s = a[i] + a[l] + a[r];10 if (s === 0) {11 out.push([a[i], a[l++], a[r--]]);12 while (l < r && a[l] === a[l - 1]) l++;13 while (l < r && a[r] === a[r + 1]) r--;14 } else s < 0 ? l++ : r--;15 }16 }17 return out;18}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1class Solution {2 public List<List<Integer>> threeSum(int[] nums) {3 Arrays.sort(nums);4 List<List<Integer>> ans = new ArrayList<>();5 int n = nums.length;6 for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) {7 if (i > 0 && nums[i] == nums[i - 1]) {8 continue;9 }10 int j = i + 1, k = n - 1;11 while (j < k) {12 int x = nums[i] + nums[j] + nums[k];13 if (x < 0) {14 ++j;15 } else if (x > 0) {16 --k;17 } else {18 ans.add(List.of(nums[i], nums[j++], nums[k--]));19 while (j < k && nums[j] == nums[j - 1]) {20 ++j;21 }22 while (j < k && nums[k] == nums[k + 1]) {23 --k;24 }25 }26 }27 }28 return ans;29 }30}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
三数之和 · 解法对比
找出所有和为 0 且不重复的三元组。
- 测试用例
nums = [-1,0,1,2,-1,-4]- 题目分类
- 双指针
- 解法对比
- 2
三重枚举 + 集合去重
枚举三个下标，将排序后的三元组放进集合。
- 时间
O(n³)- 空间
O(k)
排序 + 双指针
排序后固定第一个数，用左右指针寻找相反数，并跳过重复值。
- 时间
O(n²)- 空间
O(1) 除答案