题目
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:
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.
解法思路（一）
- 游标
i在[0, numbers.length - 1)中滑动的过程中，在[i + 1, numbers.length-1]中找target - numbers[i]；
解法实现（一）
时间复杂度
- O(NlogN)；
空间复杂度
- O(1)；
关键词
二分查找
package leetcode._167;
/**
* 从 i 开始遍历，然后在剩下的数组中用二分查找法找 target - numbers[i]；
* 时间复杂度：O(NlogN)
*/
public class Solution2 {
public int[] twoSum(int[] numbers, int target) {
for(int i = 0; i < numbers.length - 1; i++) {
int j = binarySearch(numbers, i + 1, numbers.length-1, target - numbers[i]);
if (j != -1) {
return new int[] {i+1, j+1};
}
}
return null;
}
private int binarySearch(int[] numbers, int l, int r, int target) {
while (l <= r) {
int mid = (l + r)/2;
if (numbers[mid] == target) {
return mid;
} else if (numbers[mid] < target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] numbers = {2, 7, 11, 15};
int[] result = (new Solution2()).twoSum(numbers, 9);
for(int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
}
算法思路（二）
- 指针对撞；
- 两个指针
i和j分别从数组的两端向中间逼近，比较两个指针所指元素之和与target的大小；
解法实现（二）
时间复杂度
- O(N)；
空间复杂度
- O(1)；
关键词
对撞指针
package leetcode._167;
/**
* 对撞指针
* 时间复杂度：O(N)
* 空间复杂度：O(1)
*/
public class Solution3 {
public int[] twoSum(int[] numbers, int target) {
int i = 0, r = numbers.length - 1;
while (i < r) {
if (numbers[i] + numbers[r] == target) {
return new int[]{i + 1, r + 1};
} else if (numbers[i] + numbers[r] < target) {
i ++;
} else {
r --;
}
}
return null;
}
public static void main(String[] args) {
int[] numbers = {2, 7, 11, 15};
int[] result = (new Solution3()).twoSum(numbers, 9);
for(int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
}
