双指针
解题思路
由于 numbers 是有序数组，则可以定义 left、right 两个指针分别指向数组的头和尾；
当
numbers[left] + numbers[right] > target则说明右边在值太大right--；当
numbers[left] + numbers[right] < target则说明左边在值太小left++；
复杂度
-
时间复杂度：
O(N) -
空间复杂度：
O(1)
代码实现
var twoSum = function (numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
if (numbers[left] + numbers[right] > target) {
right--;
} else if (numbers[left] + numbers[right] < target) {
left++;
} else {
return [left + 1, right + 1];
}
}
};
二分查找
解题思路
第一层迭代 固定第一个数 K；
第二层利用 二分查找 查找等于
target - K的另一个数 M；停止循环，返回
[K+1、M+1]；
复杂度
-
时间复杂度：
O(nlogn)，其中第一层迭代的时间复杂度为O(n)，第二层的二分查找时间复杂度为O(logn) -
空间复杂度：
O(1)
代码实现
var twoSum = function (numbers, target) {
let left = 0,
right = numbers.length - 1;
for (let i = 0; i < numbers.length; i++) {
left = i + 1;
while (left <= right) {
let mid = left + Math.floor((right - left) >> 1);
if (numbers[i] + numbers[mid] < target) {
left = mid + 1;
} else if (numbers[i] + numbers[mid] > target) {
right = mid - 1;
} else {
return [i + 1, mid + 1];
}
}
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 450. 删除二叉搜索树中的节点
上一篇
评论
