两数之和 II - 输入有序数组
# 📃 题目描述
题目链接:
- 剑指 Offer II 006. 排序数组中两个数字之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 167. 两数之和 II - 输入有序数组 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个已按照 升序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ,所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字,同时一个数字不能使用两次。
示例 1:
输入:numbers = [1,2,4,6,10], target = 8
输出:[1,3]
解释:2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
# 🔔 解题思路
不同于 1. 两数之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 这道用哈希表做的题目(当然你按照哈希表的做法去做也没问题),本题要求第一个数一定要在第二个数的左边,并且,更重要的是,数组已经是有序的!(有序且包含重复元素,各位可能马上就想到了可以用二分查找,固定一个数,二分查找另一个数,显然这样效率不是很高)
我们使用两个指针,一个指向数组开头,一个指向数组结尾:
- 若两个指针指向的数之和 < target,left 右移;
- 若两个指针指向的数之和 > target,right 左移;
class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0 || numbers[0] > target) {
return new int[0];
}
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left, right};
}
else if (sum < target) {
left ++;
}
else {
right --;
}
}
return new int[0];
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10