167. Two Sum II - Input Array Is Sorted
## description
## 167. Two Sum II - Input Array Is Sorted
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
1Input: numbers = [2,7,11,15], target = 9
2Output: [1,2]
3Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].Example 2:
1Input: numbers = [2,3,4], target = 6
2Output: [1,3]
3Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].Example 3:
1Input: numbers = [-1,0], target = -1
2Output: [1,2]
3Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].- –2 <= numbers.length <= 3 * 104
- –-1000 <= numbers[i] <= 1000
- –numbers is sorted in non-decreasing order.
- –-1000 <= target <= 1000
- –The tests are generated such that there is exactly one solution.
Constraints:
## notes
### Intuition
With a sorted array, we can leverage binary search. For each number, its complement (target - curr) must be in the sorted subarray to its right, making binary search an efficient lookup method.
### Implementation
Iterate through the array. For each element, calculate its complement and perform binary search on the elements to the right. If found, return the 1-indexed pair. If not found, continue to the next element.
### Edge-cases
The problem guarantees exactly one solution exists, so we don't need to handle the case of no valid pair. Remember to return 1-based indices as required.
- –Time: O(n log n) — binary search for each element
- –Space: O(1) — only tracking pointers
### Complexity
## solution
1from typing import List
2
3class Solution:
4 def twoSum(self, numbers: List[int], target: int) -> List[int]:
5 for i in range(len(numbers)):
6 curr = numbers[i]
7 complement = target - curr
8 l, r = i + 1, len(numbers) - 1
9 while l <= r:
10 m = (l + r) // 2
11 if numbers[m] == complement:
12 return [i + 1, m + 1] # 1-based indexing
13 elif numbers[m] < complement:
14 l = m + 1
15 else:
16 r = m - 1
17
18
19 print("should not get here, check testcases")
20 return [0, 0]
21
22
23
24
25if __name__ == "__main__":
26 # Include one-off tests here or debugging logic that can be run by running this file
27 # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
28 solution = Solution()
29