滑动窗口算法攻克子数组和子串难题

滑动窗口算法攻克子数组和子串难题

滑动窗口本质上是一种同向双指针技巧。下面通过具体题目来理解其应用。

一、长度最小的子数组

题目链接：长度最小的子数组

题目解析

给定一个包含 n 个正整数的数组 nums 和一个正整数 target，找出数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

算法思路

暴力枚举

初次遇到子数组/子串问题时，容易想到暴力枚举所有子数组并判断是否满足条件。若满足且长度小于当前最优解，则更新结果。

暴力解法存在冗余操作：当 right 第一次找到满足条件的位置并更新结果后，left++，right 从 left 位置再重新遍历。实际上，如果 [0, 3] 区间刚满足条件，那么 [1, 1] 和 [1, 2] 一定不满足条件，只有 [1, 3] 才有可能满足。因此不需要重新从头遍历。

为了省略不必要的步骤，可以定义变量 sum 实时记录区间 [left, right] 的和。只需在 right 向后遍历和 left 更新时，顺手更新 sum 的值即可。

滑动窗口

滑动窗口优化了暴力枚举中不必要的部分。right 和 left 在遍历更新的过程中维护了一段区间 [left, right]，该区间像窗口一样在数组中滑动。

整体思路：

1. 进窗口：让 right 向右遍历，更新区间 [left, right] 的和 sum。
2. 出窗口：如果当前区间满足条件（区间和大于等于 target），就更新结果，然后让 left++，并更新区间和，重复上述操作直到区间不满足条件。
3. 更新结果：根据题目要求决定何时更新结果。

代码实现

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