【滑动窗口】209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
● 进阶：如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题思路：
● 方式一：滑动窗口。 时间复杂度：O(n)
设立指针i，j，初始化下标均为0。j 不断后移，并且计算当前窗口的和sum，直到sum ≥ target。此时后移i指针，并更新sum，直到无法再移动 i 。重复上述步骤，直到 j 完成遍历。在此过程中记录滑动窗口的最小值。
● 方式二：数组前缀和 + 二分查找 时间复杂度：O(nlogn)
由于该数组是一个正整数数组，计算出来的前缀和数组sums一定是一个递增数组，满足二分条件。
定义sums[i] = nums[1] + nums[2] + …… + nums[i];
则sums[n] - sums[m] = nums[m+1] + nums[m+2] + …… + nums[n].（此时不包含nums[m]）
问题需求：sums[n] - sums[m] >= target，等价于sums[m] + target <= sums[n]。
此时问题可以转换为，当固定开始下标为m+1时，target(新) = sums[m] + target(旧)，在递增数组sums中找到第一个≥target(新)的元素下标。
（ $\color{red}{注意：下标为m的元素，会在减法的时候被移除，所以并不包含在内。}$ ）
（ $\color{red}{因此，sums数组的长度为nums.length + 1，保证下标为0的元素也可以作为开始元素。}$ ）
举例：
sums[0] + target(旧) → 找到从下标1开始的满足题意的最小长度
sums[1] + target(旧) → 找到从下标2开始的满足题意的最小长度
……
sums[n-2] + target(旧) → 找到从下标n-1开始的满足题意的最小长度（n为数组长度）
⭕【sums[n-1]也要被计算，因为虽然sums[n-1]不作为开始下标，但是可以作为结束下标，从另一个角度说，需要把全部元素的和计算一遍】

⭐ 对上述结果观察，可以发现nums[0]没有被包括进来，所以我们要重新修改sums的定义。
定义sums[i] = nums[1] + nums[2] + …… + nums[i-1];
则sums[n] - sums[m] = nums[m] + nums[m+1] + …… + nums[n].（此时包含nums[m]）
问题需求【不变】：sums[n] - sums[m] >= target，等价于sums[m] + target <= sums[n]。
此时问题可以转换为，当固定开始下标为【m】时，target(新) = sums[m] + target(旧)，在递增数组sums中找到第一个≥target(新)的元素下标。
举例：
sums[0] + target(旧) → 找到从下标0开始的满足题意的最小长度
sums[1] + target(旧) → 找到从下标1开始的满足题意的最小长度
……
sums[n-1] + target(旧) → 找到从下标n-1开始的满足题意的最小长度（n为数组长度）
⭕【sums[n]也要被计算，因为虽然sums[n-1]不作为开始下标，但是可以作为结束下标，从另一个角度说，需要把全部元素的和计算一遍】！
因此，通过遍历每一个sums元素【为了固定开始下标】，调用二分查找，并在此过程中记录最小的长度，即可完成所求。

Java

● 方式一
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i = 0;
        int j = 0;
        int sum = 0;
        int result = nums.length;
        while(j < nums.length){
            sum += nums[j];
            if(sum >= target){
                
                // 尝试移动i指针
                int tmp = (sum-nums[i]);
                while(tmp >= target){
                    sum = tmp;
                    i++;
                    tmp = (sum-nums[i]);
                }

                tmp = j - i + 1;
                if(result > tmp) result = tmp;

            }
            j++;
        }
        
        if(sum < target) return 0;
        else return result;
    }
}

● 方式二
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum[] = new int[nums.length + 1];
        sum[0] = 0; // 包括nums[0]
        for(int i=1; i<sum.length; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int result = Integer.MAX_VALUE;
        // 开始固定开始下标
        for(int i=0; i<nums.length; i++){
            int newTarget = target + sum[i];
            // 二分查找sums递增数组：找到第一个比newTarget大的元素下标
            int l =  i;
            int r = sum.length - 1;
            int mid = l + (r - l) / 2;
            while(l <= r){
                mid = l + (r - l) / 2;
                if(sum[mid] < newTarget){
                    l = mid + 1;
                }else{ // sum[mid] >= newTarget
                    r = mid - 1; // 保证下标为l的是正确的
                }
            }
            if(l >= sum.length) continue; // 说明找不到
            int curLen = l - i; // sum[t] 不包括 num[t]
            if(result > curLen) result = curLen;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}