Why it works
- Fix one number, nums[i], and the other two must add up to -nums[i]. In a sorted array that is Two Sum II: left and right walk towards each other, and each move rules a number out for good.
- After sorting, equal numbers stand side by side, so a repeat is easy to spot. If nums[i] equals the number before it, its triples are already found and i skips it; after a found triple, left steps over the copies of its middle number the same way.
- Each triple is found once, when i first stands on its smallest number: the loop tries every first number, and the pair search sees every pair to the right of it.
Complexity
Time O(n²): sorting takes O(n log n), then for each of the n values of i the pointers cross the rest of the array once. Memory O(1) not counting the answer: the array is sorted in place, and no set is needed to catch repeats.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗