长度最小的子数组209

地址：https://leetcode.cn/problems/queue-reconstruction-by-height/?envType=problem-list-v2&envId=segment-tree

题干

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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 <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 104

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

一眼滑动窗口。因为暴力解也没法AC了，只介绍滑动窗口以及优化题解。

关于滑动窗口建议多练几次，练一下写法，这样会很快。

滑动窗口的核心思想是，不断的调节子序列的起始位置和终止位置。我们应该将滑动窗口遍历起点定在窗口的左边界还是右边界？左边界，其实就是暴力解，右边界就不同了，右指针不断向右移动，扩大窗口，把新元素加入 sum.

信息

右指针不断向右移动，扩大窗口，把新元素加入 sum。

当 sum >= target 时，说明当前窗口满足条件，我们尝试收缩左边界，即把左指针向右移动，同时从 sum 中减去移出的元素，看看能否得到一个更短的满足条件的窗口。

在收缩过程中，记录下每次满足条件时的窗口长度，并更新最小长度。

重复直到右指针遍历完整个数组。

题解

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 滑动窗口
        int minVal = INT32_MAX;// 比对值
        int sum = 0;// 总和
        int lptr = 0;// 起始位置
        int winLen = 0;// 窗口长度
        for(int rptr=0;rptr<nums.size();++rptr){
            sum+=nums[rptr];
            while(sum>=target){
                // 监控窗口内的数组，只要总和大于等于target
                winLen = rptr-lptr+1;// 为什么要＋1？因为这两个指针涵盖的值都要包括
                minVal = (minVal<winLen)?minVal:winLen;//更新窗口长度最小值
                sum -= nums[lptr++];
            }
        }
        return minVal==INT32_MAX?0:minVal;
    }
};

滑动窗口模板

int slidingWindow(vector<int>& nums, int target) {
    int left = 0, right = 0;
    int sum = 0; // 或其它需要维护的状态
    int ans = ...; // 根据题目要求初始化
    
    while (right < nums.size()) {
        // 扩大窗口：将 nums[right] 加入窗口
        sum += nums[right]; // 或其他操作
        right++;
        
        // 当窗口需要收缩时（视题目条件而定）
        while (/* 窗口需要收缩的条件 */) {
            // 更新答案（如果需要）
            ans = ...;
            // 缩小窗口：移出 nums[left]
            sum -= nums[left];
            left++;
        }
        // 可能也需要在这里更新答案（取决于题目）
    }
    return ans;
}