3Sum asks for all unique triplets that sum to zero. The algorithm is short; the part interviewers watch is how you avoid duplicate triplets without a hash set of tuples.
Sorting costs O(n log n), which is cheaper than the O(n^2) scan that follows, and it unlocks two things: two pointers, and skipping equal neighbours to remove duplicates.
For each index i, look for two numbers in nums[i+1:] that sum to -nums[i]. Move lo up when the sum is too small and hi down when it is too large.
def three_sum(nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if nums[i] > 0: break
if i and nums[i] == nums[i-1]: continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s < 0: lo += 1
elif s > 0: hi -= 1
else:
res.append([nums[i], nums[lo], nums[hi]])
lo += 1
while lo < hi and nums[lo] == nums[lo-1]: lo += 1
hi -= 1
return res
Two skips handle everything: skip a fixed value equal to the previous fixed value, and after a match, advance lo past equal values. The early break when nums[i] > 0 is a cheap optimisation worth mentioning.
3Sum Closest uses the same loop and tracks the best distance. 4Sum adds one more fixed index and generalises to kSum by recursion down to the two-pointer base case. Total time for 3Sum is O(n^2) with O(1) extra space besides the output.
If you practise explaining patterns like this out loud, an AI interview assistant can prompt you when you skip a step. Disclosure: I help build Linkjob AI.