和为s的两个数
- .
- 题目链接
- 题目详情
- 算法原理
- 我的答案
.
题目链接
和为s的两个数
题目详情
算法原理
这里我们是利用单调性来使用双指针的对撞指针来解决问题
因为数组给的是有序递增的,因此我们设置两个指针left和right来解决问题,当nums[left]与nums[right]相加会有三种情况:
- nums[left]+nums[right]>target
当满足这种情况的时候,在[left,right]这个区间中,right与最小的left相加都大于target,那么right与left右边的数相加也是必然会大于target的,由此,此时的right已经没有继续校验的价值了,使用right–跳过即可 - nums[left]+nums[right]<target
当满足这种情况的时候,在[left,right]这个区间中,left与最大的right相加都小于target,那么left与right左边的数相加也是必然会小于target的,由此,此时的left已经没有继续校验的价值了,使用left++跳过即可 - nums[left]+nums[right]=target
此时就是找到了目标两数,将两返回即可
我的答案
class Solution {
public int[] twoSum(int[] price, int target) {
int left = 0,right = price.length-1;
while(left<right){
if(price[left]+price[right]>target){
right--;
}else if(price[left]+price[right]<target){
left++;
}else{
return new int[]{price[left],price[right]};
}
}
return new int[]{0};
}
}