Two Sum With One or All Pairs
Given a list of integers nums and an integer target, find indices of two different elements whose values add up to target.
Implement one method for input containing exactly one valid pair and another method for input that may contain multiple valid pairs, including pairs formed using repeated values.
Method Signatures
Find One Unique Pair
List<Integer> twoSum(List<Integer> nums, int target)
- Use this method when exactly one valid pair exists.
- Return the two indices as
[i, j], where i < j.
- The same element cannot be selected twice.
Find All Pairs
List<String> twoSumAll(List<Integer> nums, int target)
- Return every valid pair of indices.
- Represent each pair as a string in the format
"i,j".
- Each pair must satisfy
i < j.
- Return an empty list when no valid pair exists.
Output Ordering
For twoSumAll, sort the pairs by their first index in ascending order. If multiple pairs have the same first index, sort them by their second index in ascending order.
Rules
- An element cannot be paired with itself.
- Repeated values at different indices are separate elements.
- Each distinct pair of indices must appear at most once.
- Every returned pair must satisfy
nums.get(i) + nums.get(j) == target.
Constraints
2 ≤ nums.size() ≤ 10,000-1,000,000,000 ≤ nums.get(i) ≤ 1,000,000,000-1,000,000,000 ≤ target ≤ 1,000,000,000- Input passed to
twoSum contains exactly one valid pair.
- Input passed to
twoSumAll may contain zero or more valid pairs.
Examples
Example 1: One Unique Pair
twoSum(nums = List.of(4, 12, 7, 1), target = 8)
Output: [2, 3]
The values at indices 2 and 3 are 7 and 1, whose sum is 8.
Example 2: One Pair Using Repeated Values
twoSum(nums = List.of(6, 3, 9, 6), target = 12)
Output: [0, 3]
The two occurrences of 6 are at different indices and may be selected together.
Example 3: Multiple Pairs
twoSumAll(nums = List.of(4, 1, 5, 3, 3, 7, -1), target = 6)
Output: ["1,2", "3,4", "5,6"]
The corresponding value pairs are 1 + 5, 3 + 3, and 7 + (-1).
Example 4: Repeated Pairs
twoSumAll(nums = List.of(2, 2, 2, 2), target = 4)
Output: ["0,1", "0,2", "0,3", "1,2", "1,3", "2,3"]
Every pair of different indices is valid even though all elements have the same value.
Example 5: No Pair
twoSumAll(nums = List.of(10, -3, 6, 1), target = 20)
Output: []
No two different elements add up to 20.