三数之和
3Sum
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums，判断是否存在三元组 [a, b, c] 满足 a + b + c = 0，请返回所有不重复的三元组。
示例：nums = [-1, 0, 1, 2, -1, -4]，输出 [[-1, -1, 2], [-1, 0, 1]]。
解题思路
- 先排序是关键预处理：排序后可以用双指针扫配对，也便于跳过重复元素。
- 固定最小数 nums[i]，在右侧区间用左右双指针找和为 -nums[i] 的两个数：和偏小移左指针，偏大移右指针。
- 去重三处：i 跳过与前一个相同的值；找到一组解后，左指针跳过重复值、右指针跳过重复值。
- 排序后若 nums[i] > 0 可直接终止——三个正数之和不可能为零。
参考实现
查看参考实现Python · 建议先自行作答
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
res.append([nums[i], nums[l], nums[r]])
# 跳过重复的左右元素
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return res