长度最小的子数组

长度最小的子数组

滑动窗口法

滑动窗口类似于双指针法，也是使用双指针，但是类似一个窗口根据不同条件在原数组上滑动。

滑动窗口的确定主要三点:

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int subLength = 0;
        int result = Integer.MAX_VALUE;
        for(;right< nums.length;right++){
            sum += nums[right];
            while(sum >= target){
                subLength = right - left +1;
                // 寻找最小区间
                result = result < subLength ? result : subLength;
                //起始位置往前缩小
                sum -= nums[left++];
            }
        }
        // 若 result未被赋值，则取0
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

滑动窗口求解模版

最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。

1
2
3
4
5
6
while j < (nums.length):
    //判断[i, j]是否满足条件
    while (满足条件)：
        //更新结果
        i += 1 //最大程度的压缩i，使得滑窗尽可能的小
    j += 1

最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。

1
2
3
4
5
6
while (j < nums.length):
    //判断[i, j]是否满足条件
    while (不满足条件)：
        i += 1 //保守的压缩i，一旦满足条件了就退出压缩i的过程
    //更新结果（注意在while外更新！）
    j += 1