双指针+了一点小小小的优化:
class Solution {public int[] twoSum(int[] numbers, int target) {int left=0;int right=numbers.length-1;while(left<=right){int mediate=left+(right-left)/2;if(numbers[left]+numbers[right]==target) return new int[] {left+1,right+1};else if(numbers[left]+numbers[right]<target){if(numbers[mediate]+numbers[right]<target) left=mediate+1;else if(numbers[mediate]+numbers[right]>target) left=left+1;else return new int[] {mediate+1,right+1};}else if(numbers[left]+numbers[right]>target){if(numbers[mediate]+numbers[left]>target) right=mediate-1;else if(numbers[mediate]+numbers[left]<target) right=right-1;else return new int[] {left+1,mediate+1};}}return null;}}
看见了一个很妙的写法,可以用二分法确定右边的范围,然后用双指针来确定最终结果。
class Solution {public int[] twoSum(int[] numbers, int target) {if(numbers==null) return null;int tail=Dichotomy(numbers,target-numbers[0]);int head=0;while(head<tail){int sum=numbers[head]+numbers[tail];if(sum==target) return new int[]{head+1,tail+1};else if(sum<target) head++;else tail--; }return null;}private int Dichotomy(int[] numbers,int target){//找到了最接近目标值的下标int left=0;int right=numbers.length-1;while(left<=right){int mediate=left+(right-left)/2;if(numbers[mediate]==target) return mediate;else if(numbers[mediate]>target) right=mediate-1;else left=mediate+1;}return left-1;//即返回的num[left-1]<target}}
如果nums[i]>target-nums[0]
的话,则nums[i]以及右边肯定不是所求。
我们需要nums[i]<=target-nums[0]
。而Dichotomy解决的就是这个问题。
也了解了,由于+的优先级高于>>,所以8+(10)>>1
结果是9,而不是13.
如果觉得《167.两数之和Ⅱ-输入有序数组》对你有帮助,请点赞、收藏,并留下你的观点哦!