LeetCode167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

1
2
3
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.

Two pointers

my code in cpp

1
2
3
4
5
6
vector<int> twoSum(vector<int>& numbers, int target) {
int l = 0, r = numbers.size() - 1;
while (numbers[l] + numbers[r] != target)
if (numbers[l] + numbers[r] > target) r--;
else l++;
return{ l + 1,r + 1 };}

总结

未命名3

  1. 数组是有序的,而且一定能找到pair。所以设两个指针,一前一后向中间遍历。
  2. 如果和大于target,右指针向左移动一格;如果和小于target,左指针向右移动一格。
Thanks for Support.