Leetcode Answers 167

继续作死,这也是一道双pointer/index的问题,是Two Sum的一个升级版。

题目:
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 and you may not use the same element twice.

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

思路:
毕竟是Easy的题,既然list已经是sort了,那么对于每一个数字,前一个必然不大于它,后一个必然不小于它,那么就和看到了一颗二叉树差不多,找两个index,一个从前面往后找,一个从后面往前面找,两个inde指向的数字的和比target大,则后面的index继续向前,比target小,则前面的index继续向后移,正好最好,没有就没有了。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int[] TwoSum(int[] numbers, int target) {
int first = 0, last = numbers.Length - 1;
while(first < last){
if(numbers[first] + numbers[last] == target){
return new int[]{ first + 1, last + 1};
}
else if(numbers[first] + numbers[last] < target){
first++;
}else{
last--;
}
}
return new int[]{ -1, -1 };
}
}

以上。

17-04-23
@Sturbridge