題目
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]；
解法實現(xiàn)（一）
時間復雜度
- O(NlogN)；
空間復雜度
- O(1)；
關(guān)鍵詞
二分查找
package leetcode._167;
/**
* 從 i 開始遍歷，然后在剩下的數(shù)組中用二分查找法找 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分別從數(shù)組的兩端向中間逼近，比較兩個指針所指元素之和與target的大??；
解法實現(xiàn)（二）
時間復雜度
- O(N)；
空間復雜度
- O(1)；
關(guān)鍵詞
對撞指針
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]);
}
}
}
