定长 K 的滑动窗口思路

当题目中给出了一个确切的数字 K，要求在大小为 K 的范围内寻找答案时，可以通过维护一个固定长度的窗口来简化问题的求解。这个方法非常适用于需要在固定大小的子数组或子字符串中进行统计或判断的问题。

套用思路

• 固定窗口大小：因为窗口的长度是 K，我们可以使用两个指针 l 和 r，分别表示窗口的左右边界。通过保持 r - l + 1 = K 来保证窗口的大小为 K。
• 窗口滑动：当窗口的长度固定后，我们通过移动 l 和 r 来遍历所有可能的窗口，并在每次移动时更新窗口内的信息（如字符频次、子数组和等）。

关键细节

1. 如何创建一个固定长度为 K 的窗口:

   • 使用双指针 l 和 r（分别表示窗口的左边界和右边界）。
   • 初始化时，l = 0 且 r = K - 1，此时窗口大小刚好是 K。
   • 然后通过移动 l 和 r 来滑动窗口，保持 r - l + 1 = K。

2. 如何维护这个窗口:

   • 窗口在滑动过程中，可以通过固定的长度 K 来调整窗口内的数据。
   • 移动窗口时，增加新进入窗口的元素，同时移除离开窗口的元素，以保持窗口中的统计信息。
   • 遍历方式:
     • 最简单的方法是让 l 遍历所有可能的位置，同时调整 r 使得 r = l + K - 1。这种方式会枚举所有大小为 K 的窗口，但可能会出现重复或者不需要的情况。
     • 优化方式：当某些条件满足时才移动 l，并在每次移动时更新窗口的统计信息。比如，如果一个字符的出现频次过多，可以缩小窗口；如果频次不够，则扩展窗口。

举例题目

定长子串中元音的最大数目

给你字符串 s 和整数 k，请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的元音字母为（a, e, i, o, u）。

示例

• 示例 1：

  • 输入：s = "abciiidef", k = 3
  • 输出：3
  • 解释：子字符串 "iii" 包含 3 个元音字母。

• 示例 2：

  • 输入：s = "aeiou", k = 2
  • 输出：2
  • 解释：任意长度为 2 的子字符串都包含 2 个元音字母。

• 示例 3：

  • 输入：s = "leetcode", k = 3
  • 输出：2
  • 解释："lee"、"eet" 和 "ode" 都包含 2 个元音字母。

• 示例 4：

  • 输入：s = "rhythms", k = 4
  • 输出：0
  • 解释：字符串 s 中不含任何元音字母。

• 示例 5：

  • 输入：s = "tryhard", k = 4
  • 输出：1

代码实现

class Solution {
    public int maxVowels(String s, int k) {
        int l = 0; // 窗口左边界
        int r = 0; // 窗口右边界
        int len = s.length();
        int ans = 0; // 存储最大元音数目
        int nows = 0; // 当前窗口内元音字符数

        while (r < len) {
            // 如果窗口长度大于等于k，移除左边界的字符
            if (r - l >= k) {
                if (isVowel(s.charAt(l))) nows--;
                l++;
            }

            // 加入右边界的字符
            if (isVowel(s.charAt(r))) nows++;

            // 更新最大值
            ans = Math.max(nows, ans);
            
            r++;
        }

        return ans;
    }

    // 判断是否是元音字符的辅助函数
    private boolean isVowel(char ch) {
        return ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u';
    }
}

当然这个 K 不一定是 r - l，也可能是一种条件，在满足这种条件的时候，应该如何去移动窗口。