1 / 4思路
3Sum
思路
先排序。固定第一个数 nums[i],在它右边用双指针找两数之和为 -nums[i]。排序后相同的数相邻,固定项和双指针都要跳过重复值,避免重复三元组。
复杂度
- 时间 O(n^2):外层 n 次,内层双指针 O(n)。
- 空间 O(1):不计排序和结果。
代码
- Python
- TypeScript
def three_sum(nums: list[int]) -> list[list[int]]:
nums.sort()
result: list[list[int]] = []
for i, value in enumerate(nums):
if i > 0 and value == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = value + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([value, 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
return result
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const result: number[][] = [];
for (let i = 0; i < nums.length - 2; i += 1) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
let left = i + 1;
let right = nums.length - 1;
while (left < right) {
const total = nums[i] + nums[left] + nums[right];
if (total < 0) left += 1;
else if (total > 0) right -= 1;
else {
result.push([nums[i], nums[left], nums[right]]);
left += 1;
right -= 1;
while (left < right && nums[left] === nums[left - 1]) left += 1;
while (left < right && nums[right] === nums[right + 1]) right -= 1;
}
}
}
return result;
}
边界
- 少于三个数:返回空。
- 全为 0:只返回一个
[0, 0, 0]。 - 固定项去重与双指针去重必须同时做,否则会重复。