解析
15 3Sum
- 排序后，如何保证插入结果集的triplet不重复？
- Approach 1: 用一个set来记录已经插入结果集的triplet，如果当前triplet已经存在于set中，那么就跳过该triplet
- Approach 2:
- 对于左边的指针，
if (i > 0 && nums[i] == nums[i - 1]) continue;- 比如 [-2, -2, 0, 2] 的情况，如果不加这个判断，那么会出现两个[-2, 0, 2]的triplet
- 对于中间的指针，
while nums[m] == nums[m-1] m += 1- 比如 [-2, 0, 0, 2, 2] 的情况，如果不加这个判断，那么会出现两个[-2, 0, 2]的triplet
- 对于左边的指针，
# solution 1 - 左右指针
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
# time: 0(n * n)
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]: # to skip duplicates, e.g., [-1, -1, 0, 1]
continue
l, r = i + 1, len(nums) - 1
while l < r:
cur_sum = nums[i] + nums[l] + nums[r]
if cur_sum == 0:
res.append([nums[i], nums[l], nums[r]])
r -= 1
while l < r and nums[r] == nums[r + 1]: # to skip duplicates, e.g., [-1, 0, 1, 1]
r -= 1
elif cur_sum > 0:
r -= 1 # move r to the left, to decrease cur_sum
else:
l += 1 # move l to the right, to increase cur_sum
return res
ref
167. Two Sum II - Input Array Is Sorted
# solution 1 - 左右指针