3Sum

Sort the list first. Then any three positions i < j < k give values that are already in order, nums[i] ≤ nums[j] ≤ nums[k], so a triplet is written correctly the moment you find it. Three nested loops visit every choice of positions, so no triplet can be missed.

Repeats come next. The first example sorted is [-2, -1, 0, 1, 1, 2], and [-1, 0, 1] can take its 1 from index 3 or index 4. Each loop therefore skips a position whose value equals the one that same loop tried before it. Every loop then tries each distinct value once, and every distinct triplet comes out once, already in sorted order. The skip only compares with the previous position inside the same loop, so [-2, 1, 1] still uses both ones.

The cost is the problem. There are about n³/6 triples: for 3000 numbers that is 4.5 × 10^9 sums, far beyond any time limit.

Once the first value nums[i] is fixed, you need two later values that add up to -nums[i]. That is Two Sum. Walk j to the right of i and keep a set of the values you have passed. At each j the missing value is need = -nums[i] - nums[j]. If need is in the set, [nums[i], need, nums[j]] adds up to 0. A set lookup costs O(1) on average, so one i costs O(n) and the whole search O(n²).

Sorting still does the bookkeeping. Skip an i whose value equals the one before it. After a match, move j past every copy of nums[j]: with the first and third values fixed, the middle one is fixed too, so another copy could only repeat the same triplet. Since need comes from an earlier position of the sorted list, need ≤ nums[j] and the triplet is in order. You can also stop as soon as nums[i] > 0: the two values after it are at least as large, so the sum cannot reach 0.

One detail: as j moves right, nums[j] grows and need shrinks, so the triplets for one i come out with the middle value going down. In [-2, -1, 0, 1, 1, 2] with i = 0, you find [-2, 1, 1] at the second 1 and then [-2, 0, 2] at the 2. Reverse each group before you add it to the answer. The C and R versions mark seen values in an array indexed by value instead of a hash set, which works because every value lies within ±10^5.

The sorted order can replace the set. Fix nums[i], put lo at i+1 and hi at the last index, and look at nums[i] + nums[lo] + nums[hi]. Below 0, you need a larger value, so lo moves right. Above 0, you need a smaller one, so hi moves left. At exactly 0, record the triplet and move both.

No triplet is lost. When the sum is below 0, nums[lo] falls short even with the largest value left, nums[hi], so it cannot pair with anything still in range and dropping it loses nothing. Above 0 is the mirror case: nums[hi] is too large even with the smallest value left. Every step drops one value for good, so one i costs at most n steps and the whole search O(n²), with no memory beyond the sort and the output.

Take the sorted [-2, -1, 0, 1, 1, 2]. With i = 0 (value -2), lo starts at -1 and hi at 2: the sum is -1, so lo moves to 0. Now -2 + 0 + 2 = 0, so you record [-2, 0, 2] and both pointers land on the two 1s, which give [-2, 1, 1]. With i = 1 (value -1), 0 and 2 give 1, so hi moves to the second 1, and -1 + 0 + 1 = 0 records [-1, 0, 1]. The value 0 at i = 2 finds nothing, and at i = 3 the value is positive, so the search stops.

Repeats need two rules. Skip an i whose value equals the one before it. After a match, step lo past copies of the value it used. hi needs no rule of its own: with lo on a larger value, a copy of the old nums[hi] now gives a sum above 0 and moves away by itself. Because i visits the distinct values in increasing order and lo only moves right, the triplets come out sorted.