Two Pointers
Fix one, scan the rest
Turning a three-element search into a two-element one, and handling duplicates without a set.
Key idea
The reduction
Searching for three elements that satisfy a condition looks like a different problem from searching for two. It is not. Fix the first element, and what remains is a two-element search with an adjusted target, which you can already do in O(n).
Doing that for every possible first element gives O(n) choices times O(n) inner scan, so O(n squared) overall. That is the expected complexity for this family, and it beats the O(n cubed) triple loop by exactly the amount the inner two-pointer scan saves.
Tip
Why the inner scan starts at `i + 1`
Starting the inner pointers to the right of i is what prevents reusing an element and what prevents finding the same combination in a different order. Every triple is discovered exactly once, in increasing index order.
That is the same reason the inner loop of an all-pairs scan starts at i + 1 rather than 0. If you ever find yourself dividing a count by two to fix double counting, check whether the bound should have prevented it in the first place.
Why it works
Skipping duplicate values
Counting index triples and listing distinct value triples are different questions, and the second one is where duplicates bite. If the input holds two 2s, the same set of values can be reached through different indexes, and a problem asking for distinct results wants it reported once.
The fix is to skip repeated values at each level rather than to deduplicate the results afterward. Sort first so equal values sit together, then at each level, if this value equals the previous one at the same level, move on.
Gotcha
Deduplicating afterward is the wrong fix
Collecting everything and then removing duplicates does produce the right answer, and it costs extra memory and hides the actual issue. It also forces you to make results hashable just to put them in a set, which for lists means converting to tuples and back.
Skipping at the source is a two-line change and leaves the complexity alone. Interviewers ask about duplicate handling specifically because the difference between these two answers is informative.
Edge cases
Skip after recording, not before
The skip loop runs after a match is recorded. Skipping before checking would step over the first member of a run, which is the one you want to keep.
Check the boundary too. sorted_values[left - 1] is only safe once left has advanced at least once, which it has here because the skip is inside the branch that already incremented it.
Find the duplicate-handling bug
This is meant to return each distinct pair once. On the input [1, 1, 2, 2, 3, 3] with target 4 it returns [[1, 3], [1, 3], [2, 2]]. Click the line that causes the repeat.
This activity type is not wired up yet.
Cost of fix-one-then-scan
Give the time and space complexity of count_triples_summing_to on an already sorted list of length n, not counting the output.
Time
Space
3sum
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.