LeetCode Two Sum II - Input array is sorted

LeetCode 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. 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


本题要在一个已排序数组中找两个数,使得这两个数的和等于一个目标target。这应该是LeetCode Two Sum的简化版吧,因为之前那个题有一种解法就是先对数组排序,然后首尾指针夹逼,现在这个题都排好序了,那还有什么好说的呢,直接借用之前的方法。

完整代码如下:

class Solution {
public:
	vector<int> twoSum(vector<int>& numbers, int target) {
		int i = 0, j = numbers.size() - 1;
		while (numbers[i] + numbers[j] != target) {
			if (numbers[i] + numbers[j] > target)--j;
			else ++i;
		}
		return vector<int>({ i + 1,j + 1 });
	}
};

本代码提交AC,用时9MS。

Leave a Reply

Your email address will not be published. Required fields are marked *