目录

🔍 ​​一、算法核心原理​​

​​1. 基本概念​​

​​2. 操作步骤​​

​​3. 时间复杂度​​

⚙️ ​​二、典型实现模式​​

​​1. 固定大小窗口（求子数组最大值）​​

​​2. 动态大小窗口（无重复字符最长子串）​​

​​3. 条件驱动窗口（最小覆盖子串）​​

🎯 ​​三、关键应用场景​​

​​1. 子数组/子串问题​​

​​2. 固定窗口问题​​

​​3. 多条件约束问题​​

⚡ ​​四、性能优化技巧​​

🧠 ​​五、边界处理与常见错误​​

💎 ​​总结​​

---

滑动窗口（双指针）算法是处理数组/字符串子区间问题的高效技术，其核心是通过动态调整窗口边界（通常用两个指针表示）来避免重复计算，将时间复杂度优化至​​O(n)​​。以下是其在C语言中的详细实现与应用解析：

---

🔍 ​​一、算法核心原理​​

​​1. 基本概念​​

• ​​窗口定义​​：
  由左指针（left）和右指针（right）定义的闭区间 [left, right]，表示当前处理的子数组或子串。
• ​​窗口类型​​：
  • ​​固定大小窗口​​：如求长度为k的子数组最大值。
  • ​​动态大小窗口​​：如无重复字符的最长子串，窗口大小随条件变化。

​​2. 操作步骤​​

1. ​​初始化窗口​​：
   left = 0, right = 0，初始化辅助变量（如哈希表、窗口和等）。
2. ​​扩展窗口（右移right）​​：
   遍历数组，将新元素纳入窗口，更新状态（如字符计数、窗口和）。
3. ​​收缩窗口（左移left）​​：
   当窗口​​不满足条件​​时（如出现重复字符或窗口和超标），左移left缩小窗口，更新状态。
4. ​​更新结果​​：
   在每次窗口满足条件时，记录最优解（如最大长度、最小和等）。

​​3. 时间复杂度​​

• ​​O(n)​​：每个元素最多被left和right指针各访问一次。

---

⚙️ ​​二、典型实现模式​​

​​1. 固定大小窗口（求子数组最大值）​​

#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))

void maxInWindow(int nums[], int n, int k) {
    for (int i = 0; i <= n - k; i++) {
        int max = nums[i];
        for (int j = 1; j < k; j++) {
            max = MAX(max, nums[i + j]);
        }
        printf("%d ", max);
    }
}

​​适用场景​​：窗口大小固定，如滑动窗口最大值/最小值。

​​2. 动态大小窗口（无重复字符最长子串）​​

#include <string.h>

int lengthOfLongestSubstring(char* s) {
    int charIndex[128] = {0}; // 记录字符最后出现位置
    int left = 0, maxLen = 0;
    for (int right = 0; s[right]; right++) {
        char c = s[right];
        // 若字符已在窗口中，左边界移至重复字符的下一位
        if (charIndex[c] > 0 && charIndex[c] >= left) 
            left = charIndex[c];
        charIndex[c] = right + 1; // 更新字符位置
        maxLen = (right - left + 1 > maxLen) ? right - left + 1 : maxLen;
    }
    return maxLen;
}

​​关键点​​：

• 使用数组charIndex记录字符最后出现位置。
• 当charIndex[c] >= left时，说明字符在窗口内重复。

​​3. 条件驱动窗口（最小覆盖子串）​​

#include <string.h>

char* minWindow(char* s, char* t) {
    int need[128] = {0}, window[128] = {0};
    for (int i = 0; t[i]; i++) need[t[i]]++;
    int left = 0, right = 0, match = 0, minLen = INT_MAX, start = 0;
    while (s[right]) {
        char c = s[right++];
        if (need[c]) {
            window[c]++;
            if (window[c] == need[c]) match++;
        }
        while (match == strlen(t)) {
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }
            char d = s[left++];
            if (need[d]) {
                if (window[d] == need[d]) match--;
                window[d]--;
            }
        }
    }
    return (minLen == INT_MAX) ? "" : strndup(s + start, minLen);
}

​​逻辑​​：

• need数组记录目标字符频次，window记录窗口内字符频次。
• match统计匹配的字符数，当match = strlen(t)时收缩窗口。

---

🎯 ​​三、关键应用场景​​

​​1. 子数组/子串问题​​

​​问题类型​​	​​解决方法​​	​​示例​​
无重复字符最长子串	动态窗口 + 字符位置映射	LeetCode 3
最小覆盖子串	动态窗口 + 频次统计	LeetCode 76
最大子数组和	动态窗口 + 和阈值调整	LeetCode 53

​​2. 固定窗口问题​​

• ​​滑动窗口最大值/最小值​​：使用双端队列维护单调队列。
• ​​固定长度子数组平均值​​：累加窗口和后滑动计算。

​​3. 多条件约束问题​​

• ​​最多包含k种字符的最长子串​​：动态调整窗口使字符种类 ≤ k。
• ​​和至少为K的最短子数组​​：结合前缀和与双指针。

---

⚡ ​​四、性能优化技巧​​

1. ​​哈希表优化​​：

   • 对ASCII字符用数组代替哈希表（如int map[128]），减少哈希冲突。
   • Unicode字符可用uthash库实现动态哈希。

2. ​​提前终止条件​​：当窗口长度已小于当前最优解时，跳过后续扩展。

3. ​​状态复用​​：在固定窗口问题中，用window_sum = window_sum - nums[left] + nums[right]避免重复求和。

---

🧠 ​​五、边界处理与常见错误​​

1. ​​指针越界​​：
   循环条件需确保right < strlen(s)，避免访问无效内存。

2. ​​空输入处理​​：
   若输入字符串为空，直接返回0。

3. ​​频次统计误差​​：
   收缩窗口时需先检查window[d] == need[d]再减少match，防止误判。

4. ​​初始化陷阱​​：
   字符位置数组charIndex需初始化为0，表示未出现过。

---

💎 ​​总结​​

滑动窗口算法通过​​双指针动态维护窗口边界​​，结合​​哈希表​​或​​数组​​记录状态，将复杂问题的时间复杂度优化至​​O(n)​​。其核心在于：

1. ​​扩展与收缩的平衡​​：右指针探索新数据，左指针优化解空间。
2. ​​状态同步更新​​：窗口移动时需实时维护字符频次、位置等信息。
3. ​​适用场景广泛​​：从字符串匹配到数值数组处理，覆盖高频面试题型。

实际应用中，需根据问题特点选择固定/动态窗口模式，并严格处理边界条件。更多经典例题可参考LeetCode滑动窗口专题。