167. Two Sum II - Input array is sorted在一个升序数组中找出两个数加和等于特定值Python & Java

给定一个已经按升序排序的整数数组，请找到两个数字，使它们加起来成为一个特定的目标数字。

函数twoSum应该返回两个数字的索引，以使它们加起来等于目标，其中index1必须小于index2。

注意： 返回的答案（index1和index2）都不基于零。 可以假设每个输入都只有一个解决方案，并且可能不会两次使用同一元素。

Input：numbers = [2,7,11,15], target = 9

Output: [1,2] (2+7=9)

首先看到这个题觉得这和1.two sum有什么区别么，只是return的时候需要+1，测试完之后成功了，但是提交时超过了时间限制，测试数据搞了好几百个0在前面=+=

所以有了下面这个，时间复杂度O(n)

class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l=0
r=len(numbers)-1
while l<r:
s=numbers[l]+numbers[r]
if s==target:
return [l+1,r+1]
elif s<target: #因为是有序数组，所以当sum值小于target时就换左面第二小的
l+=1
else:
r-=1

Java

和python同样的思路

class Solution {
public int[] twoSum(int[] numbers, int target) {
int i = 0, l = numbers.length-1;
while (i < l) {
if (numbers[i] + numbers[l]==target) {
return new int[]{i+1,l+1};
} else if (numbers[i] + numbers[l] < target) {
i++;
} else {
l--;
}
}
return new int[]{};
}
}

时间复杂度O(n)超级快哦

最后

以上就是腼腆书本为你收集整理的167. Two Sum II - Input array is sorted在一个升序数组中找出两个数加和等于特定值Python & Java的全部内容，希望文章能够帮你解决167. Two Sum II - Input array is sorted在一个升序数组中找出两个数加和等于特定值Python & Java所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。