209. 长度最小的子数组

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

方法一：

设置左右两个指针，起点都为0

右指针不断的前进，计算两个指针之间的元素和

当元素和的大小大于等于目标值时，判断能否在保证元素和大于目标值的同时，移动左指针前进

计算当前这种左右区间的长度，更新最小区间长度的答案

注意边界：如果所有元素的和都小于目标值，则区间不存在，返回0

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        // 滑动窗口
        int l = 0, n = nums.length;
        int sum = 0;
        int res = n;

        for(int r = 0 ; r < n; ++ r){
            sum += nums[r];
            if(sum >= target){
                while(sum - nums[l] >= target) {
                    sum -= nums[l++];
                }
                res = Math.min(res, r - l + 1);
            }
        }
        if(sum < target) return 0;
        return res;
    }
}

方法二：前缀和+二分查找

我们的目标是找到一个最小长度区间内元素和大于等于target

一个简单的想法是枚举区间的左右端点，这样复杂度是 $O(n^2)$

但是如果我们只枚举左端点，右端点使用二分查找的方式，复杂度为 $O(nlog(n))$

由于前缀和是不断递增的，满足二分查找的条件，所以我们只需要找到一个索引最小的右端点，使得左右端点之间的元素和大于等于target

public class Solution2 {
    public int minSubArrayLen(int target, int[] nums) {
        // 前缀和&二分查找：nlog(n)
//        System.out.println(Arrays.toString(nums));
        int n = nums.length;
        int[] sums = new int[n+1];
        sums[0] = 0;
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i-1];
        }
        int res = n;
        for (int i = 1; i <= n; i++) {
            int minr = binarySearch(sums, i, n, target);
            if(minr != -1){
                res = Math.min(res, minr - i + 1);
            }
//            System.out.println(i + ", " + minr);
        }
        return sums[n] < target ? 0 : res;
    }

    // lowerBound: mid偏左，< 判断里左指针+1
    public int binarySearch(int[] sums, int i, int n, int target){
        int l = i, r = n;
        while(l < r){
            int mid = (l + r) >> 1;
            if(sums[mid] - sums[i - 1] < target){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return sums[l] - sums[i - 1] < target ? -1 : l;
    }
}