题目:LeetCode209. 长度最小的子数组

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

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

LeetCode209. 长度最小的子数组-LMLPHP
思路:
滑动窗口
接下来就开始介绍数组操作中另一个重要的方法:滑动窗口。

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

在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环 完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考 如果用一个for循环,那么应该表示 滑动窗口的起始位置,还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置,那么如何遍历剩下的终止位置?

此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。

在本题中实现滑动窗口,主要确定如下三点:

窗口内是什么?
如何移动窗口的起始位置?
如何移动窗口的结束位置?
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

解题的关键在于 窗口的起始位置如何移动,如图所示:
LeetCode209. 长度最小的子数组-LMLPHP
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int i=0;
        int sum=0;
        int length=Integer.MAX_VALUE;
        for (int j = 0; j < nums.length; j++) {
            sum+=nums[j];
            while(sum>=target)
            {
                length=(j-i+1)<length?(j-i+1):length;
                sum-=nums[i++];
            }
        }
        return length=length==Integer.MAX_VALUE?0:length;
    }
}
08-11 15:41