You are given a list of integers nums, sorted from smallest to largest (equal neighbours are
allowed), and an integer target. Find two different positions i and j whose numbers add up
to target, and return them as [i, j] with i < j. Indices count from 0.
At least one such pair exists; if several do, any one of them is accepted. Try to use only a constant amount of extra memory.
Example 1
- Input
- nums = [1, 3, 4, 6, 9], target = 10
- Output
- [0, 4]
1 + 9 is 10. [2, 3] (4 + 6) would be accepted too.Example 2
- Input
- nums = [-5, -2, -2, 7], target = -4
- Output
- [1, 2]
Constraints
numsholds 2 to 3 × 10⁴ numbers, sorted in non-decreasing order.- Every number is between −10⁹ and 10⁹.
- At least one pair adds up to
target.
Show the pattern
Two pointers
The list is sorted, so the sum of the two ends tells you which end to move: too small, move the left end up; too big, move the right end down. Each move rules out one number for good.
See two pointers in a visualiserShow the approach
Put left at 0 and right at the last index. If nums[left] + nums[right] equals the target,
return [left, right]. If the sum is too small, nums[left] can't be in any answer (even the
largest number left isn't big enough for it), so move left right. If the sum is too big,
nums[right] can't be in any answer, so move right left.
Every step rules out one number for good, so the indices meet within n steps, and nothing is stored besides the two indices.
Time: O(n) · Space: O(1)