Every Index Pair That Sums to a Target
Problem statement
Given an integer array nums (values may repeat) and an integer target, find every pair of positions i < j with nums[i] + nums[j] == target.
Return the pairs as [i, j], sorted by i and then by j. Pairs with the same values at different positions are all listed. A position cannot be paired with itself. Return an empty list if there are none.
Function
allPairIndexes(nums: int[], target: int) → int[][]Examples
Example 1
nums = [3,5,3,1,5]target = 8return = [[0,1],[0,4],[1,2],[2,4]]Each of the two 3s (indexes 0 and 2) pairs with each of the two 5s (indexes 1 and 4), giving four pairs. Written smaller index first and sorted: [0, 1], [0, 4], [1, 2], [2, 4]. The 1 would need a 7.
Example 2
nums = [4,4,4]target = 8return = [[0,1],[0,2],[1,2]]Any two of the three 4s add up to 8: [0, 1], [0, 2], [1, 2]. One position cannot be used twice.
Example 3
nums = [2,7,-1]target = 4return = []No two values add up to 4 (2 + 7 = 9, 2 + (-1) = 1, 7 + (-1) = 6), so the answer is empty.
Constraints
2 <= nums.length <= 2000-10^9 <= nums[i] <= 10^9-2 * 10^9 <= target <= 2 * 10^9- the answer has at most 1500 pairs