[LeetCode] Two Sum II - Input array is sorted

Problem Description:

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. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Well, have you finished the Two Sum problem? What will happen if the input array is sorted. Well, the key is, in this case, each target will be composed of two numbers, one in the left half of the array and the other in the right half of the array. You may need to think a while and convince yourself of this by some examples.

Then we simply need to set two pointers, one starts from 0 and the other starts from numbers.size() - 1. If the numbers pointed by them sum to target, we are done. Otherwise, if the sum is larger than the target, we know the number in the right half is larger and we need to move the right pointer to the left by 1. The case is similar if the sum is smaller.

So we could write down the following code.

 1     vector<int> twoSum(vector<int> &numbers, int target) {
 2         int left = 0, right = numbers.size() - 1;
 3         while (left < right) {
 4             if (numbers[left] + numbers[right] == target)
 5                 return {left + 1, right + 1};
 6             if (numbers[left] + numbers[right] > target)
 7                 right--;
 8             else left++;
 9         }
10     }

[LeetCode] Two Sum II - Input array is sorted

原文：http://www.cnblogs.com/jcliBlogger/p/4562235.html