All Pairs With a Given Sum
You are given an integer array nums and an integer target.
Find every pair of indices [i, j] where i < j and nums[i] + nums[j] == target.
Return the pairs as a list of two-element lists. Sort the list by i, and when two pairs have the same i, by j. If there is no such pair, return an empty list.
Note
Pairs are made of indices, not values. If the same value appears more than once, each different pair of positions is a separate answer.
Checking every pair is fine for small inputs. A faster way keeps a map from each value to the indices where it was seen, so for each j you can find all matching i directly.
Examples
Example 1
- Input:
- [3,1,4,2,3], 5
- Output:
- [[0,3],[1,2],[3,4]]
3 + 2 = 5 (indices 0 and 3), 1 + 4 = 5 (indices 1 and 2), and 2 + 3 = 5 (indices 3 and 4). The list is sorted by the first index.
Example 2
- Input:
- [2,2,2], 4
- Output:
- [[0,1],[0,2],[1,2]]
All three values are equal, so every pair of positions adds up to 4.
Example 3
- Input:
- [1,5,-3], 10
- Output:
- []
No two numbers add up to 10, so the answer is an empty list.
Constraints
1 <= nums.length <= 12-10 <= nums[i] <= 10-20 <= target <= 20
Run checks your code against the 3 examples. Submit checks it against all 303 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.