Description
Find two different positions in a nondecreasing integer array that total target. Return their 1-based indices. Assume exactly one valid pair exists.
Solution
def two_sum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total < target:
left += 1
else:
right -= 1
return []Examples
Example 1
- Input
[[2,7,11,15],9]- Output
[1,2]
2 + 7 equals 9.
Example 2
- Input
[[-3,-1,2,4],1]- Output
[1,4]
-3 + 4 equals 1.
Example 3
- Input
[[0,0],0]- Output
[1,2]
Use both distinct positions.
Approach
Start pointers at opposite ends. If their sum is too small, move the left pointer right; if too large, move the right pointer left. Sorting guarantees each move discards only impossible pairs.
Time & space
O(n) time and O(1) auxiliary space, where n is the array length.