3Sum
Given an integer array `nums`, return all unique triplets `[nums[i], nums[j], nums[k]]` such that `i`, `j`, and `k` are distinct indices and `nums[i] + nums[j] + nums[k] == 0`. The solution set must not contain duplicate triplets. **Core Insight:** Sort the array. Fix one element `nums[i]` and use the two-pointer technique on the remaining subarray to find pairs that sum to `-nums[i]`. Sorting lets us skip duplicates efficiently by checking if the current element equals the previous one. **Algorithm:** Sort `nums`. For each index `i` (skip if `nums[i] == nums[i-1]`): set `left = i+1`, `right = n-1`. While `left < right`: compute sum. If sum == 0 record the triplet and advance both pointers (skipping duplicates). If sum < 0 advance `left`. If sum > 0 retreat `right`. **Complexity:** Time O(n²) — O(n log n) sort plus O(n) two-pointer scan for each of the n elements. Space O(1) extra (ignoring output).
Constraints
- •
3 ≤ nums.length ≤ 3000
def threeSum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif total < 0: left += 1
else: right -= 1
return result