209. Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, …, numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

滑动窗口，先取最左侧数字。记录窗口的最小值。
如果小于目标值，则右侧窗口向右移动，扩大窗口。更新窗口内的值。
如果大于等于目标值，则左侧窗口向右移动，缩小窗口。更新窗口内的值。
同时如果窗口大小小于最小值则更新窗口最小值。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = nums[0];
        while(right < nums.length){
            if(sum >= target){
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
            else{
                right++;
                if(right < nums.length) sum += nums[right];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

计算前缀和。
前缀和[j]与前缀和的[i]的差就是i+1到j的和。
因此需要找到sum[j] - sum[i] >= k。
暴力枚举的话需要O(n^2^)的时间复杂度。

由于前缀和是有序的，因此我们可以采用二分搜索。
寻找sum[j] - k >= sum[i]。
Arrays.binarySearch方法可以返回查找到的目录。
如果没有该值，方法会返回一个负数，其取反（x取反相当于[-(x+1)]）的值就是应该插入的目录。
将ans设置为无限大，如果(index - i)小于最小值则更新到ans。

时间复杂度O(nlogn)。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int[] sum = new int[nums.length+1];
        for(int i = 1; i <= nums.length; i++){
            sum[i] = sum[i-1] + nums[i-1];
        }
        
        int ans = Integer.MAX_VALUE;
        for(int i = 0; i < sum.length; i++){
            int search = sum[i] + target;
            int index = Arrays.binarySearch(sum, search);
            if(index < 0){
                index = ~index;
            }
            if(index < sum.length){
                ans = Math.min(ans, index - i);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}