Skip to main content

1 / 4思路

3Sum

原题

思路​

先排序。固定第一个数 nums[i],在它右边用双指针找两数之和为 -nums[i]。排序后相同的数相邻,固定项和双指针都要跳过重复值,避免重复三元组。

复杂度​

  • 时间 O(n^2):外层 n 次,内层双指针 O(n)。
  • 空间 O(1):不计排序和结果。

代码​

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

边界​

  • 少于三个数:返回空。
  • 全为 0:只返回一个 [0, 0, 0]。
  • 固定项去重与双指针去重必须同时做,否则会重复。