这篇题解主要是总结一下不定长滑动窗口的几种题型，以及基本的解法：

1.不定长滑动窗口求最长/最大

模板

ans 在 while 外更新（先保证合法再算）

for (int right = 0; right < n; right++) {
  // 1. 【进】更新窗口数据 (例如: cnt[s[right]]++)

  // 2. 【出】一旦不合法，左边界收缩直到合法
  while (窗口不合法) {
    // (例如: cnt[s[left]]--)
    left++;
  }

  // 3. 【算】此时窗口合法，更新最大长度
  ans = Math.max(ans, right - left + 1);
}

ans 在 while 内更新（先保证满足条件再缩）。

for (int right = 0; right < n; right++) {
  // 1. 【进】更新窗口数据

  // 2. 【算】只要合法，就尝试更新最小值并收缩左边界
  while (窗口合法/满足条件) {
    ans = Math.min(ans, right - left + 1);
    // 【出】尝试移出左边界 (例如: cnt[s[left]]--)
    left++;
  }
}

这两种思路都可以，个人感觉第一种好理解。

例题

1695. 删除子数组的最大得分

这道题要求我们找到一个子数组，这个子数组的各个元素不一样，且之和是最大的。

思路

找子数组的最大和，我们可以使用滑动窗口：

• 使用哈希表/数组统计元素出现的次数防止重复即可
• 这道题的数据范围不大可以使用数组

class Solution {
  public int maximumUniqueSubarray(int[] nums) {
    int mx = 0;
    //找最大的数，目的为了明确开多大的数组
    for (int x : nums) {
      mx = Math.max(mx, x);
    }
		
    boolean[] has = new boolean[mx + 1];
    int ans = 0, s = 0, left = 0;
    for (int x : nums) {
      
      //核心思路
      while (has[x]) {//发现了此时枚举的数重复了
        has[nums[left]] = false;//尝试移动left指针，直到重复消除
        s -= nums[left];
        left++;
      }
      has[x] = true;
      s += x;//维护窗口的元素和
      ans = Math.max(ans, s);//更新最大元素和
    }
    return ans;
  }
}

2.不定长滑动窗口求最短/最小

模板

跟求最长/最大是类似的，只不过要反过来

在 while 循环内更新答案

// 初始化 ans = n + 1
for (int right = 0; right < n; right++) {
  sum += nums[right]; // 【进】

  // 【算 & 缩】只要满足要求，就先记录答案，再尝试收缩
  while (sum >= target) { 
    ans = Math.min(ans, right - left + 1); // 先记下
    sum -= nums[left];                     // 再尝试缩
    left++;
  }
}

while循环之后更新答案

// 初始化 ans = n + 1
for (int right = 0; right < n; right++) {
  sum += nums[right]; // 【进】

  // 【缩】只要减去左边界后依然满足条件，就一直缩
  while (sum - nums[left] >= target) { 
    sum -= nums[left];
    left++;
  }

  // 【算】此时窗口是：以 right 为结尾且满足条件的“最紧凑”窗口
  if (sum >= target) {
    ans = Math.min(ans, right - left + 1);
  }
}

这两种思路都可以，我个人感觉第一种好理解。

例题

209. 长度最小的子数组

这道题要求我们找到>= target ，且长度最小的子数组

思路

找满足条件的最短子数组，可以使用滑动窗口

class Solution {
  public int minSubArrayLen(int target, int[] nums) {
    //找出满足其总和大于等于 target 的长度最小的子数组,返回长度，否则返回0
    int n = nums.length;
    int left = 0;
    int s = 0;
    int ans = n+1;
    
    for(int right = 0; right < n; right++){
      s += nums[right];
      if(s < target){
        continue;
      }
      //核心代码
      
      while(s >= target){//发现满足情况之后，尝试缩小窗口
        //1. 更新答案
        ans = Math.min(ans , right - left + 1);
        //2. 然后开始收缩
        s -= nums[left];
        left++;
      }
    }
    return ans <= n ? ans : 0;

  }
}

3.求子数组的个数

3.1越长越合法

核心思路

这类题的核心思路如下：

• while循环结束之后，窗口[left,right]这个子数组是不满足条件的，因为left最后也执行了++操作，而退出循环之前的最后一轮循环，[left-1,right]是满足条件的，子数组越长越满足条件，所以[left-2,right]，[left-3,right]，一直到[0,right]都是满足条件的，这一共有left个满足条件的子数组

• 所以一般跳出循环之后，更新答案要写：ans += left

例题

1358. 包含所有三种字符的子字符串数目

字符串 s ，它只包含三种字符 a, b 和 c 。题目要求找 a，b 和 c都至少出现过一次的子字符串数目

class Solution {
  public int numberOfSubstrings(String S) {
    int [] cnt = new int[3];
    char s[] = S.toCharArray();
    int n = s.length;
    int left = 0;
    int ans = 0;
    for(int right = 0 ; right < n; right++){
      int c = s[right];
      cnt[c - 'a']++;
      //核心代码
      while(cnt[0] > 0 && cnt[1] > 0 && cnt[2] >0 ){//发现满足条件，尝试收缩窗口，直到不满足
        cnt[s[left] - 'a']--;
        left ++;
      }
      //此时[left,right]是不满足条件的，[0,right],[1,right]......[left-1,right]都是满足的，一共有left个
      ans += left;
    }
    return ans;
  }
}

3.2越短越合法

核心思路

这类题的核心思路如下：

• while循环结束之后，窗口[left,right]这个子数组是满足条件的，由于子数组越短，越能满足题目要求，所以除了 [left,right]，[left+1,right],[left+2,right],…,一直到[right,right] 都是满足要求的。这一共有right - left + 1个

• 所以一般跳出循环之后，更新答案要写：ans += right - left + 1

例题

713. 乘积小于 K 的子数组

题目要求找：子数组所有元素的乘积严格小于 k 的连续子数组的数目

class Solution {
  public int numSubarrayProductLessThanK(int[] nums, int k) {
    if(k<=1){
      return 0;
    }

    int n = nums.length;
    int sum = 1;
    int left = 0;
    int ans = 0;
    for(int right = 0; right < n;right++){
      //维护窗口的乘积
      sum*=nums[right];
      
      //核心代码
      while(sum>=k){//发现不满足条件，尝试收缩窗口，直到满足条件
        sum /= nums[left];
        left++;
      }
      //此时[left,right]是满足条件的，[left+1,right],[left+2,right]一直到[right,right]都是满足条件的，这一共有right - left +1个
      ans += right - left +1;
    }
    return ans;

  }
}

3.3恰好型（越短越合法的变体）

核心思路

这类题主要是进行了问题转换：

• 要计算有多少个元素和恰好等于 k 的子数组，可以把问题变成：
  • 算有多少个元素和 ≥k 的子数组。
  • 计算有多少个元素和 ≥k+1 的子数组。
• 恰好等于 k 的子数组个数 = ≥k 的子数组个数 - ≥k+1 的子数组个数

而恰好型，变成求两个"至少"的相减，这其实就是 3.2 越短越合法 的变体

[!tip]

注意

• 这种方式主要适用于单调性明确的问题（如元素均为非负数）。
• 如果数组中包含负数，滑动窗口的单调性会被破坏，此时通常需要使用 前缀和 + 哈希表 来解决。

对应的题：560. 和为 K 的子数组 （注意：有负数，所以不能用滑动窗口，只能使用前缀和 + 哈希表）

例题

930. 和相同的二元子数组

题目要求统计并返回有多少个和为 goal 的 非空 子数组。

/*
	统计并返回有多少个和为 goal 的 非空 子数组。
*/
class Solution {
  public int numSubarraysWithSum(int[] nums, int goal) {
    // 「和恰好为goal的子数组数量」=「和最多为goal的子数组数量-和最多为goal-1的子数组数量
    return atMost(nums, goal) - atMost(nums, goal - 1);
  }

  // 滑动窗口。计算和最多为goal的子数组数量
  private int atMost(int[] nums, int goal) {
    if (goal < 0)  return 0;
    int l = 0, r = 0, sum = 0, res = 0;
    while (r < nums.length) {
      // 1、扩大窗口
      sum += nums[r];
      // 2、缩小窗口
      while (sum > goal) {
        sum -= nums[l];
        l++;
      }
      // 3、更新答案
      // 当前窗口[l,r]内所有以r为结尾的子数组都满足条件
      res += r - l + 1;
      r++;
    }
    return res;
  }
}

总结

滑动窗口的本质是双指针在单向移动。对于初学者，如果能理解 right 指针负责“探索”，left 指针负责“止损/修正”

滑动窗口题单推荐：

• 力扣灵茶山艾府滑窗题单

如果这篇博客对你有帮助，欢迎点赞、收藏！