3Sum
The key idea
Sort the array, then fix one number and shrink the remaining sub-array from both ends with two pointers. The sorted order lets you move
left right to grow the sum or right left to shrink it, turning a 3-loop search into a fixed loop plus a linear two-pointer scan, and it makes skipping duplicates a simple neighbor check.Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets. The triplets may be returned in any order.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Examples
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Input: nums = [0,1,1]
Output: []
Input: nums = [0,0,0]
Output: [[0,0,0]]
Complexity
Time: O(n^2) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization