滑动窗口讲解(c基础)

1. 滑动窗口的基本概念

滑动窗口是一种高效处理线性数据结构（如数组、字符串）的算法技巧。它就像是一个可移动的 “框”，框住数据结构中的一部分元素，通过不断地移动这个 “框”（即滑动窗口），对框内的元素进行分析和处理，以解决各种与子序列、子数组相关的问题。

1. 滑动窗口的组成部分

• 窗口边界：
  • 通常由两个指针来定义窗口的边界，例如left和right。left指针指向窗口的左边界（起始位置），right指针指向窗口的右边界（结束位置）。通过移动这两个指针，可以控制窗口的大小和位置。
• 窗口大小：
  • 可以是固定大小，也可以是根据特定规则动态变化的。在固定大小的滑动窗口中，窗口大小在整个算法过程中保持不变；而在动态大小的滑动窗口中，窗口大小会根据问题的要求和窗口内元素的性质进行调整。
• 窗口内容：
  • 即窗口边界所包含的元素集合。对这些元素可以进行各种操作，如求和、计数、检查是否满足某种条件等。

1. 滑动窗口的操作步骤（以一般情况为例）

• 初始化窗口：

  • 首先要确定窗口的初始位置和大小。这可能涉及到将left和right指针初始化为合适的位置，以及初始化一些用于记录窗口相关信息的变量，如窗口内元素的和、计数等。
  • 例如，在固定大小滑动窗口求数组中固定长度子数组的最大和的问题中，初始窗口的和是通过一个循环计算前k个元素的和得到的，此时left = 0，right = k - 1。

• 滑动窗口：

  • 扩展窗口（右移right指针）：
    • 通常，在窗口尚未完全遍历数据结构时，需要不断地向右移动right指针来扩大窗口。在这个过程中，需要更新窗口内元素的相关信息，如将新进入窗口的元素计入总和、计数等操作。
    • 例如，在寻找包含特定字符集合的最小子串的问题中，当right指针右移时，要将新进入窗口的字符在窗口字符计数数组中的计数加 1，并检查是否满足包含所有目标字符的条件。
  • 收缩窗口（左移left指针）：
    • 当窗口满足某些条件（如已经包含了足够的元素、达到了某个阈值等）时，可能需要收缩窗口，即左移left指针。在左移过程中，要相应地更新窗口内元素的信息，如将移出窗口的元素从总和、计数中减去。
    • 例如，在最小覆盖子串问题中，当窗口已经包含了目标字符串中的所有字符时，尝试左移left指针来缩小窗口，同时更新窗口状态，直到窗口不再满足包含所有目标字符的条件为止。

• 更新结果（根据问题要求）：

  • 在窗口滑动的过程中，根据问题的具体要求，可能需要不断地更新结果。例如，在求子数组最大和的问题中，每次更新窗口和后，需要比较当前窗口和与最大和，若当前窗口和更大，则更新最大和；在求最小覆盖子串的问题中，每次收缩窗口时，需要比较当前窗口长度与最小窗口长度，若当前窗口长度更小且满足条件，则更新最小窗口长度和起始位置。

• 终止条件：

  • 滑动窗口的操作会在满足一定条件时停止。最常见的情况是right指针到达数据结构的末尾。例如，在遍历完整个数组或者字符串后，滑动窗口的过程结束。

1. 示例 - 固定大小滑动窗口（求数组中固定长度子数组的最大和）详细讲解

• 代码回顾：

  • 展开过程

收起

plaintext

复制

- **初始化窗口（第1 - 7行）**：
    - 首先，函数检查数组`nums`的大小`numsSize`是否小于给定的子数组长度`k`。如果是，那么不存在长度为`k`的子数组，直接返回0。
    - 接着，通过一个循环（第4 - 6行）计算初始窗口（前`k`个元素）的和，将其存储在`window_sum`变量中。同时，将`max_sum`也初始化为这个窗口和的值，因为此时它是目前找到的最大和（因为还没有开始滑动窗口）。
- **滑动窗口（第8 - 13行）**：
    - 从第`k`个元素开始（索引为`k - 1`），进入`for`循环（第8 - 13行），这个循环控制窗口的滑动。在每次循环中，通过`window_sum = window_sum - nums[i - k] + nums[i]`来更新窗口内元素的和。
    - 具体来说，`window_sum - nums[i - k]`这部分是减去窗口最左边滑出的元素（因为窗口向右滑动了一个位置，最左边的元素就离开了窗口）。例如，当`i = k`时，`nums[i - k]`就是初始窗口的第一个元素`nums[0]`。然后`+ nums[i]`这部分是添加新进入窗口的元素，此时`nums[i]`就是窗口向右滑动一个位置后新进入窗口的元素。
- **更新结果（第11 - 12行）**：
    - 在每次更新窗口和之后，比较`window_sum`和`max_sum`的大小。如果`window_sum`大于`max_sum`，就将`max_sum`更新为`window_sum`。这样，在整个窗口滑动过程中，`max_sum`始终记录着到目前为止长度为`k`的子数组的最大和。
- **终止条件（第8行循环条件）**：
    - 循环条件是`i < numsSize`，这意味着只要窗口的右端点（`right`指针对应的位置，即`i`）还没有超出数组的范围，窗口就会持续向右滑动。当`right`指针到达数组末尾时，循环结束，此时`max_sum`中存储的就是数组中长度为`k`的子数组的最大和，最后将其返回。

5. **示例 - 动态大小滑动窗口（寻找包含特定字符集合的最小子串）详细讲解**

- **代码回顾（简化部分初始化代码）**：
    - ```c
      char *min_window(char *s, char *t) {
          int need[128] = {0};
          int window[128] = {0};
          int left = 0, right = 0;
          int match_count = 0;
          int min_len = strlen(s) + 1;
          int min_left = 0;
          // 统计t中字符出现的次数
          for (int i = 0; i < strlen(t); i++) {
              need[t[i]]++;
          }
          while (right < strlen(s)) {
              window[s[right]]++;
              if (window[s[right]] == need[s[right]]) {
                  match_count++;
              }
              while (match_count == strlen(t)) {
                  if (right - left + 1 < min_len) {
                      min_len = right - left + 1;
                      min_left = left;
                  }
                  window[s[left]]--;
                  if (window[s[left]] < need[s[left]] {
                      match_count--;
                  }
                  left++;
              }
              right++;
          }
          if (min_len <= strlen(s)) {
              char *result = (char *)malloc((min_len + 1) * sizeof(char));
              strncpy(result, s + min_left, min_len);
              result[min_len] = '\0';
              return result;
          } else {
              return "";
          }
      }

• 初始化窗口（第 1 - 7 行和第 10 - 11 行）：
  • 定义了两个数组need和window，分别用于记录目标字符串t中字符出现的次数和滑动窗口内字符出现的次数。这两个数组的大小为 128，足以覆盖 ASCII 码表中的常见字符。
  • 初始化了窗口边界指针left和right为 0，表示窗口初始位置在字符串s的开头。同时初始化了match_count为 0，用于记录窗口内已经匹配上t中字符的个数；min_len为strlen(s) + 1，用于记录最小子串的长度，初始值设为一个较大的值；min_left为 0，用于记录最小子串的起始位置。
  • 通过一个循环（第 10 - 11 行）统计字符串t中字符出现的次数，存储在need数组中。
• 滑动窗口（第 12 - 22 行）：
  • 扩展窗口（第 13 - 15 行）：
    • 在主while循环（第 12 - 22 行）中，首先不断右移right指针（第 17 行）来扩大窗口。每次将新进入窗口的字符在window数组中的计数加 1（第 14 行）。
    • 然后检查窗口内该字符的计数是否等于need数组中该字符的计数，如果是，则将match_count加 1（第 15 行），表示又匹配上了一个t中的字符。
  • 收缩窗口（第 16 - 21 行）：
    • 当match_count等于t的长度时，说明窗口内已经包含了t中所有的字符，此时进入内层while循环（第 16 - 21 行）开始收缩窗口。
    • 在收缩窗口过程中，首先检查当前窗口长度（right - left + 1）是否小于min_len，如果是，则更新min_len和min_left（第 18 - 19 行），记录下当前更小的子串。
    • 接着，将窗口左边界left指向的字符在window数组中的计数减 1（第 20 行）。如果此时窗口内该字符的计数小于need数组中该字符的计数，那么match_count减 1（第 21 行），表示窗口不再包含t中所有的字符，停止收缩窗口。
• 更新结果（第 18 - 19 行）：
  • 在收缩窗口阶段，当窗口长度变小且仍然满足包含所有目标字符的条件时，更新min_len和min_left，这两个变量始终记录着到目前为止找到的最小子串的长度和起始位置。
• 终止条件（第 12 行循环条件）：
  • 外层while循环的条件是right < strlen(s)，这意味着只要窗口的右端点（right指针对应的位置）还没有超出字符串s的范围，窗口就会持续滑动。当right指针到达字符串末尾时，循环结束。
• 返回结果（第 23 - 28 行）：
  • 最后，根据min_len的值来返回结果。如果min_len小于等于s的长度，说明找到了满足条件的最小子串，通过malloc分配足够的内存来存储这个子串，使用strncpy函数将子串复制到新分配的内存中，并添加字符串结束符'\0'，然后返回这个结果。如果min_len大于s的长度，说明没有找到满足条件的子串，返回空字符串。