167.兩數之和Ⅱ-輸入有序數組

雙指針+了一點小小小的優化：

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.