LeetCode链接：167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）
思路一：用双指针，指针left指向0的位置，指针right指向array.length - 1的位置，当left < right时，如果left + right < targe执行left++，如果left + right > targe执行right--,如果left + right = targe返回new int[left + 1, right + 1]
时间复杂度：O(n)
java代码：
//双指针
class Solution{
public int[] twoSum(int[] numbers){
int left = 0;
int right = numbers.length - 1;
while(left < right){
if((numbers[left] + numbers[right]) > target){
right--;
}else if((numbers[left] + numbers[right]) < target){
left++;
}else{
return new int[]{left+1,right+1};
}
}
return new int[]{-1,-1};
}
}
思路二：使用二分支查找，遍历数组，用target-array[i]得出另外一个目标元素，并用二分查找法找到目标元素的位置
时间复杂度：O(nlongn)
java代码：
//二分查找
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{-1, -1};
}
}
