209. 长度最小的子数组

力扣题目链接

解题思路

首先很容易想到暴力解放,用两层for循环,不断寻找符合条件的子序列,时间复杂度为O(N^2),超时

本题可以用数组中一个重要的方法:滑动窗口

所谓滑动窗口,就是不断调节子序列的起始和终止位置,从而得出我们想要的结果.

其实本质上暴力解法中,一个for循环是滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,进而完成一个区间搜索的过程.

那么如何只遍历一次数组,来完成这个区间搜索的过程呢?

首先很明确,遍历数组的这层循环是用来控制滑动窗口的终止位置的.起始位置可以通过当前窗口的子序列的值来调节.

定义一个start和end指针,分别用来表示滑动窗口的起始和终止位置.维护变量sum来存储子序列的元素和,即(nums[start]到nums[end]的元素和).当子序列元素和大于等于目标值时,说明此序列满足,更新滑动窗口大小,并将起始位置右移来调节滑动窗口大小.

代码如下:

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n <= 0) return 0;
        int start = 0, end = 0, sum = 0;
        int ans = Integer.MAX_VALUE;
        while (end < n){
            sum += nums[end];
            while (sum >= s){
                ans = Math.min(end - start + 1, ans);
                sum -= nums[start];
                start ++;
            }
            end ++;
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
        
    }
}

滑动窗口也可以理解为双指针的一种.其中

end指针:为窗口的结束位置,也是用来遍历整个数组.

start指针为窗口的起始位置

sum维护变量,用来表示窗口结束位置到起始位置这个子序列的元素和.

当sum维护变量的大小满足题目要求时,①更新答案②把当前start指向的值从sum中减去③start指针右移