题解 | #旋转数组的最小数字#

O(N), 双指针

由于数组升序，左右指针指向首尾

左右指针相加大于sum，则右指针左移，小于sum，左指针右移使得相加等于sum

剪枝操作表示此次循环left和right指向的数值和上次循环相等，没有计算的必要，直接continue，当然也可以不用，但是这种操作可以去重（很重要），此题不要求去重，直接计算得到一个就跳出

此题有暴力解法，O(N2)

import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
    ArrayList<Integer> res = new ArrayList<>();
    //左右指针相加大于sum，则右指针左移，小于sum，左指针右移
    int left = 0;
    int right = array.length - 1;
    while(left < right){
        if(left > 0 && array[left] == array[left - 1]) {//剪枝
            left++;
            continue;
        }
        if(right < array.length - 1 && array[right] == array[right + 1]) {//剪枝
            right --;
            continue;
        }
        
        if(array[left] + array[right] > sum){
            right --;
        }else if(array[left] + array[right] < sum){
            left ++;
        }else{
            res.add(array[left]);
            res.add(array[right]);
            return res;
        }
    }
    
    return res;
}
}