Leetcode Study Day 12

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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.

My solution

My solution is initialise the first number as the variable first and the last number as the variable last. Then we add these two numbers, if they are larger than the target, we set the last number as the previous number of the last number. If they are smaller than the target, we set the first number as the next number of the first number. If they are equal to the target, we return the index of the first number and the last number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int n = numbers.size();
int j = n - 1;
int i = 0;
int first = numbers[i];
int last = numbers[j];
while (first + last != target){
if (first + last > target){
j --;
last = numbers[j];
}
else{
i++;
first = numbers[i];
}
}
vector <int> answer;
answer.push_back(i+1);
answer.push_back(j+1);
return answer;
}
};
  • Copyrights © 2020-2024 Yangyang Cui

请我喝杯咖啡吧~

支付宝
微信