LeetCode 15: 3Sum (Sorting + Two Pointers)
LeetCode 15ArrayTwo PointersInterviewToday we solve LeetCode 15 - 3Sum.
Source: https://leetcode.com/problems/3sum/
English
Problem Summary
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.
Key Insight
After sorting, we can fix one element nums[i], then solve a 2Sum problem on the suffix using two pointers. Sorting also enables deterministic duplicate skipping for i, left, and right, which is essential because the output must contain unique triplets only.
Brute Force and Why Insufficient
Brute force enumerates every triple index (i, j, k) with three nested loops, checks sum equals zero, and uses a set to deduplicate. This takes O(n^3) time, which is too slow for interview constraints and unnecessary once we exploit sorted order.
Optimal Algorithm (Step-by-Step)
1) Sort nums ascending.
2) Iterate i from 0 to n-3.
3) If i > 0 and nums[i] == nums[i-1], skip to avoid duplicate first elements.
4) Set left = i + 1, right = n - 1.
5) While left < right:
• Compute sum = nums[i] + nums[left] + nums[right].
• If sum == 0, record triplet, move both pointers, and skip duplicates on both sides.
• If sum < 0, increase left to make sum larger.
• If sum > 0, decrease right to make sum smaller.
6) Continue until all i processed.
Complexity Analysis
Time: O(n^2) after sorting (sorting is O(n log n), dominated by two-pointer scans).
Space: O(1) extra (excluding output; sorting may use implementation-dependent stack space).
Common Pitfalls
- Forgetting duplicate checks for i, creating repeated triplets.
- Not skipping duplicates after finding a valid triplet, still producing duplicates.
- Using hash-based 2Sum inside each i and losing deterministic duplicate control.
- Pointer moves in wrong direction when sum is too small/large.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return ans;
}
}func threeSum(nums []int) [][]int {
sort.Ints(nums)
ans := [][]int{}
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
ans = append(ans, []int{nums[i], nums[left], nums[right]})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if sum < 0 {
left++
} else {
right--
}
}
}
return ans
}class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < (int)nums.size() - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = (int)nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.push_back({nums[i], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) ++left;
while (left < right && nums[right] == nums[right + 1]) --right;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
}
return ans;
}
};from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
ans.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return ansvar threeSum = function(nums) {
nums.sort((a, b) => a - b);
const ans = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
ans.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return ans;
};中文
题目概述
给定整数数组 nums，找出所有不重复三元组 [nums[i], nums[j], nums[k]]，满足三者下标不同且三数之和为 0。
核心思路
先排序，再固定一个数，把剩余区间转成双指针 2Sum。排序后可以有序移动指针并且精确跳过重复值，从而同时做到“高效”与“去重正确”。
暴力解法与不足
三重循环枚举全部组合，时间复杂度 O(n^3)，即使配合集合去重，性能也很差，面试规模下容易超时。
最优算法（步骤）
1）将数组升序排序。
2）遍历下标 i 作为第一个元素。
3）若 nums[i] 与前一个相同则跳过，避免重复起点。
4）设置 left=i+1、right=n-1。
5）计算三数和：
• 等于 0：记录答案，双指针同时收缩，并跳过重复值。
• 小于 0：left++ 增大和。
• 大于 0：right-- 减小和。
6）遍历结束得到全部不重复解。
复杂度分析
时间复杂度：O(n^2)（排序 O(n log n) 后，主过程双指针扫描为平方级）。
空间复杂度：O(1) 额外空间（不计输出结果）。
常见陷阱
- 只在外层去重，内层不去重，导致重复三元组。
- 命中解后只移动一个指针，可能死循环或漏解。
- 忽略排序，直接双指针会失效。
- 指针移动方向写反，导致结果错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return ans;
}
}func threeSum(nums []int) [][]int {
sort.Ints(nums)
ans := [][]int{}
for i := 0; i < len(nums)-2; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum == 0 {
ans = append(ans, []int{nums[i], nums[left], nums[right]})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if sum < 0 {
left++
} else {
right--
}
}
}
return ans
}class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int i = 0; i < (int)nums.size() - 2; ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = (int)nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.push_back({nums[i], nums[left], nums[right]});
++left;
--right;
while (left < right && nums[left] == nums[left - 1]) ++left;
while (left < right && nums[right] == nums[right + 1]) --right;
} else if (sum < 0) {
++left;
} else {
--right;
}
}
}
return ans;
}
};from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
ans.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif s < 0:
left += 1
else:
right -= 1
return ansvar threeSum = function(nums) {
nums.sort((a, b) => a - b);
const ans = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
ans.push([nums[i], nums[left], nums[right]]);
left++;
right--;
while (left < right && nums[left] === nums[left - 1]) left++;
while (left < right && nums[right] === nums[right + 1]) right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return ans;
};
Comments