「优选算法刷题」：长度最小的子数组

一、题目

给定一个含有 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

二、思路解析

这道题也是一道很经典的 “滑动窗口” 例题，需要利用单调性，使用 “同向双指针” 来对暴力解法 「会超时」进行优化，以让时间复杂度达到要求。

但是，为何使用滑动窗口呢？

回到我们的分析对象，是「⼀段连续的区间」，我就是根据这个条件去判别的。

让滑动窗⼝满⾜：从 i 位置开始，窗⼝内所有元素的和⼩于  target （那么当窗⼝内元素之和

第⼀次⼤于等于⽬标值的时候，就是  i  位置开始，满⾜条件的最⼩⻓度）。

具体做法是，将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：

▪ 如果窗⼝内元素之和⼤于等于? target ：更新结果，并且将左端元素划出去的同时继续判

断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）

▪ 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。

最后返回最短的数值即可。

三、完整代码

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int len = Integer.MAX_VALUE;
        int n = nums.length;
        int sum = 0;
        for(int left = 0,right = 0;right < n;right++){
            sum  += nums[right];// 进窗⼝
            // 判断
            while(sum >= target){
        
                // 更新结果
                len = Math.min(len,right-left+1);
        
                // 出窗⼝
                sum -= nums[left++];
            }
        }
        return len == Integer.MAX_VALUE?0:len;
    }
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！