Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such that i≠j≠k and nums[i]+nums[j]+nums[k]==0. The solution set must not contain duplicate triplets.
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]Why sort? After sorting, if sum is too small we know moving L right (to bigger values) will increase it. If sum is too large, moving R left decreases it. This eliminates guessing.
Why skip duplicates? After sorting, duplicates are adjacent. Skipping them at both anchor and pointer levels guarantees unique triplets without a HashSet.
Why O(n²)? O(n log n) sort + outer loop O(n) × inner two-pointer O(n) = O(n²) total. Each element is visited at most once per anchor.
Three nested loops check every triplet in O(n) cubed. And you would still have to remove duplicate triplets afterwards.
First sort the array. Fix one number, then find the other two with two pointers, just like Two Sum 2. If the sum is too small, move the left pointer right, and if it is too big, move the right pointer left. Skip any value equal to the one before it, so no triplet repeats.
Sort, fix one number, two pointers for the other two. Skip equal neighbours to avoid duplicate triplets.
Run the animation above on your own input, or watch the 1:47 video explanation of 3Sum with a dry run and Java code.