Three Sum
Three Sum is a medium Two Pointers problem from the Blind 75. The key pattern is sort + two pointers, and a good solution runs in O(n²) time.
Problem
Return all unique sorted triples whose values sum to zero; sort the final list lexicographically.
Examples
Example 1
Input
[-2,0,1,1,2]Output
[[-2,0,2],[-2,1,1]]Example 2
Input
[0,1,1]Output
[]Example 3
Input
[3,-1,-2,0,1,-1]Output
[[-2,-1,3],[-1,0,1]]Approach
Sort, fix each first value, and search the rest with a left and a right pointer that move toward each other based on the current sum.
| Pattern | Sort + two pointers |
|---|---|
| Time | O(n²) |
| Space | O(1) beyond sorting |
Watch out for
Skip repeated first values and repeated pointer values after each hit so every triple appears once.