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: Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2]. Example 2: Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3]. Example 3: Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
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**.
- code
class Solution {
public int[] twoSum(int[] numbers, int target) {
int l = 0, r = numbers.length - 1;
int sum;
while (l < r){
sum = numbers[l] + numbers[r];
if (sum < target) l++;
else if (sum > target) r--;
else return new int[]{l + 1, r + 1};
}
return new int[]{0, 0};
}
}
- code
class Solution:
def twoSum(self, numbers, target):
left = 0
right = len(numbers) - 1
while numbers[left] + numbers[right] != target and left < right:
Sum = numbers[left] + numbers[right]
if Sum > target:
right = right - 1
else:
left = left + 1
if left < right:
return [left + 1, right + 1]
return []
- code same as two sum 1, not taking the advantage of sorted array.
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
dic = {}
for i in range(len(numbers)):
if numbers[i] in dic:
return [dic[numbers[i]] + 1, i + 1]
else:
dic[target - numbers[i]] = i