Core Insight Use ordering or symmetry to decide which boundary can move without discarding a valid answer.
Common Pitfall Move the pointer justified by the comparison; moving both can skip a valid pair.
Description
Find all unique triplets in the array which gives the sum of zero.
Constraints
- Time Complexity:
O(n²) - Space Complexity:
O(n)
Tags
arraytwo-pointerssorting
Implementation Plan Translate the invariant into these small, testable moves.
- Place pointers at the relevant boundaries.
- Evaluate the pair or window.
- Use the comparison to move exactly one boundary.
- Stop when the pointers cross or the target is found.
def threeSum(nums):
res = []
nums.sort()
for i, a in enumerate(nums):
if i > 0 and a == nums[i - 1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
while nums[l] == nums[l - 1] and l < r:
l += 1
return res