LeetCode 167. 两数之和 II - 输入有序数组
原题链接
中等
作者:
caichuntao
,
2023-06-20 15:14:43
,
所有人可见
,
阅读 74
方法1:二分查找
时间复杂度:$O(N*logN)$
空间复杂度:$O(1)$
解题思路
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 = low + ((high - low) >> 1);
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] < target - numbers[i]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return new int[0];
}
}