Algorithms and Data Structures · Senior · Question 64 of 75
How do you find all pairs that sum to a target in an array with duplicates, without double counting?
- 1Sort and binary search each element, adding every match found
- ✓Correct answer: Count values in a map and pair counts, handling x = target - x
- 3Put the values into a
Setand loop over it once
Explanation
For each distinct x pair it with count[target - x]; when x equals its complement use c × (c - 1) / 2. Process each value pair once (x < complement). A Set loses the counts.