167. 兩數(shù)之和 II - 輸入有序數(shù)組 - 力扣（LeetCode） (leetcode-cn.com)

難度：簡單
題目描述：給定一個已按照 非遞減順序排列 的整數(shù)數(shù)組 numbers ，請你從數(shù)組中找出兩個數(shù)滿足相加之和等于目標數(shù) target 。
函數(shù)應該以長度為 2 的整數(shù)數(shù)組的形式返回這兩個數(shù)的下標值。numbers 的下標 從 1 開始計數(shù) ，所以答案數(shù)組應當滿足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假設每個輸入 只對應唯一的答案 ，而且你 不可以 重復使用相同的元素。

分析

Java刷題隨筆---001. 兩數(shù)之和

     * 此題和001最大的區(qū)別就是輸入數(shù)組為非遞減順序排列的數(shù)組，即一個排序完成的數(shù)組。
     * 本題有兩種解題思路：
     * 1- 二分查找，而二分查找最好查找一個數(shù)，對于此題來說，二分查找的時間復雜度為O(nlogn)，空間復雜度為O(1),可以參考官方解題。
     * 2- 雙指針，本題最優(yōu)解為雙指針，時間復雜度為O(n)，空間復雜度為O(1)。
     * 雙指針的一個思路為：
     * 首先本題為非遞減順序排列的數(shù)組，可以知道數(shù)組中的值都是排序好的
     * 即numbers[i]<=numbers[i+1]恒成立
     * 本題需要找到兩個數(shù)的和等于target
     * 所以必然存在兩個數(shù) a + b = target && a <= b
     * 想要找到a b ，只需要設置兩個指針，一個指向數(shù)組頭，一個指向數(shù)組尾
     * 即i = 0, j = numbers.length - 1，
     * 此時只需要分析numbers[i] + numbers[j] 與 targe的關系即可
     * 舉例：numbers = [1,2,3,7,9], target = 9
     * 1- numbers[i] + numbers[j] > target
     * 此時 i=0, j=4, numbers[0] + numbers[4] = 10 > 9
     * 此時和數(shù)大于目標數(shù)，我們想降低和數(shù)，只能尋找小于numbers[0] 或者小于numbers[4]的數(shù)
     * 顯然尋找小于numbers[0]是不現(xiàn)實的，因為此數(shù)為最小數(shù)，所以只能尋找小于numbers[4]的數(shù)
     * 即j--
     * 2- numbers[i] + numbers[j] < target
     * 此時 i=0, j=3, numbers[0] + numbers[3] = 8 < 9
     * 和1- 同理，需要提高和數(shù)，只能尋找大于numbers[0] 或者大于numbers[3]的數(shù)
     * 所以只能尋找大于numbers[0]的數(shù)
     * 即i++
     * 3- numbers[i] + numbers[j] = target
     * 沒什么好說的，這就是最終答案，而且題目說只對應唯一的答案，所以直接返回即可
     * 一個小坑，
     * 返回數(shù)組，需要將i，j加一，因為答案中起始是1，數(shù)組中起始是0

解題

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