滑动窗口||前缀和＋二分查找 解决LeetCode209.长度最小的子数组

LeetCode.209.长度最小的子数组
给定一个含有n个正整数的数组和一个正整数target。

找出该数组中满足其总和大于等于target的长度最小的**子数组
[nums_l, nums_l+1, …, nums_r-1, nums_r]，并返回其长度。**如果不存在符合条件的子数组，返回
0。

示例 1：

输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释： 子数组[4,3]是该条件下的长度最小的子数组。

示例 2：

输入： target = 4, nums = [1,4,4]
输出： 1

示例 3：

输入： target = 11, nums = [1,1,1,1,1,1,1,1]
输出： 0

提示：

• 1 ≤ target ≤ 10⁹
• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁶

滑动窗口

• 此解法就是动态维护一个窗口，让窗口内的元素满足题目条件，且该窗口可以动态移动来穷举出所有符合题目条件的窗口。
• 结合题目，本题维护的就是窗口内元素的和，如果sum >= target，则收缩窗口，并减去移除掉元素，开始寻找下一个窗口。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0;//窗口左端l;
        int n  = nums.length;
        int sum = 0;//窗口内元素的和
        int res = Integer.MAX_VALUE;
        int windowLength = 0;//窗口长度
        //窗口右端r
        for(int r = 0; r < n; r++){
            sum += nums[r];//移动右窗口并将遍历过的元素加入窗口的和
            windowLength = r - l + 1;//计算窗口长度
            //当sum >= target时，说明已经找到了符合条件的窗口，即题目所求的子数组，此时开始收缩窗口，准备寻找下一个满足条件的窗口
            while(sum >= target){
	            //收集结果
                res = Math.min(res, r - l + 1);
                //收缩左窗口并减掉移除的元素
                sum -= nums[l];
                l++;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

前缀和 + 二分查找

• 此方法是利用nums数组构造出一个前缀和数组prefix，两个前缀和之差就是子数组元素的和。即寻找
  prefix[r] - prefix[l] >= target，若存在则说明找到了满足条件的一个子数组。将不等式变形可得
  prefix[r] >= prefix[l] + target，说明我们只要查找满足该条件的prefix[r]就好，题目要求子数组长度越短越好，则查找的下标
  r越小越好。
• 因为本题所给数组nums为正整数数组，所以前缀和数组prefix单调增，查找时可用二分查找。

nums   = [2,3,1,2,4,3]

prefix = [0,2,5,6,8,12,15]
index  = [0 1 2 3 4  5  6]

target = 7

l = 2 时：
prefix[l] = 5
need = prefix[l] + target = 5 + 7 = 12

在 prefix 中找 ≥ 12 的最小下标：
prefix[5] = 12

子数组长度 = r - l = 5 - 2 = 3
对应区间：[1,2,4]

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        //构造前缀和
        int[] prefix = new int[n + 1];
        prefix[0] = 0;
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int res = Integer.MAX_VALUE;
        //枚举左端点l
        for(int l = 0; l < n; l++){
            int need = target + prefix[l];
            int r = lowerBound(prefix,need);
            if(r != -1){
                res = Math.min(res,r - l);
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    private int lowerBound(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        int ans = -1;
		
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] >= target) {
	            //找到满足>=target的下标后先不急着返回，继续向左寻找，尽量寻找到最小的
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}