Question
You're given a list of numbers sorted in increasing order and a target value. Find two numbers that add up to the target, and return their positions (1-based).
You must solve this without using extra space — just work with the original array.
Example
Input: numbers = [1, 3, 5, 6, 9], target = 12
Output: [2, 5]
Explanation: 3 + 9 = 12
Input: numbers = [0, 2, 4, 7, 10], target = 11
Output: [3, 4]
Explanation: 4 + 7 = 11
Input: numbers = [-10, -3, 1, 2, 4], target = 1
Output: [2, 5]
Explanation: -3 + 4 = 1
My Notes
- Start with one pointer at the beginning and the other at the end.
- If the sum is equal to target, return
i+1, j+1 - If the sum is too big, move the right pointer left.
- If the sum is too small, move the left pointer right.
- Time complexity is O(n), space complexity is O(1).
package main
import (
"fmt"
)
func main() {
result := twoSum([]int{-10, -3, 1, 2, 4}, 1)
fmt.Println(result)
}
func twoSum(numbers []int, target int) []int {
i, j := 0, len(numbers) - 1
for {
if numbers[i] + numbers[j] == target {
return []int{i+1, j+1}
}
if numbers[j] + numbers[i] > target {
j--
continue
}
if numbers[i] < target {
i++
}
}
}