Triplets That Hit the Target
MediumTwo Pointers
Problem
A budgeting tool wants every way to pick three expenses from nums (three different positions) whose amounts add up exactly to target.
Return all distinct value triplets [a, b, c]. Two triplets are the same if they contain the same values; the order of the triplets and of the values inside each triplet does not matter.
Example 1
- Input:
- nums = [-2, 0, 1, 1, 2, -1], target = 0
- Output:
- [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Each triplet sums to 0, and no other combination of values does.
Example 2
- Input:
- nums = [3, 1, 5, 2], target = 12
- Output:
- []
The largest triplet sum is 5 + 3 + 2 = 10.
Example 3
- Input:
- nums = [0, 0, 0, 0], target = 0
- Output:
- [[0, 0, 0]]
Constraints
- 0 ≤ nums.length ≤ 3000
- -10^5 ≤ nums[i] ≤ 10^5
- -3·10^5 ≤ target ≤ 3·10^5
Hint
Show the first hint
If you fix the first value of the triplet, what problem is left for the other two?
Walkthrough
How to approach it
01Clarify before coding
- Distinct by values or by positions? By values: [-2, 1, 1] appears once even if there were several ways to pick the 1s.
- Can a value be reused? Only if it appears at more than one position.
- Does the order of output matter? No, neither inside a triplet nor across triplets.
02Brute force
Try all triples of indices, sort each matching triple and put it in a set to remove duplicates.
Cost: O(n³) time: about 4.5·10^9 triples for n = 3000, hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.