滑动窗口算法实战：从长度最小子数组到最小覆盖子串

1、209 长度最小的子数组

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

代码实现 (C)

int minSubArrayLen(int target, int* nums, int numsSize) {
    int left = 0, right = 0;
    int sum = 0;
    int min_len = INT_MAX;
    for (right = 0; right < numsSize; right++) {
        sum += nums[right];
        while (sum >= target) {
            min_len = fmin(min_len, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    return (min_len == INT_MAX) ? 0 : min_len;
}

时间复杂度：O(n) 空间复杂度：O(1)

核心原理：滑动窗口

滑动窗口本质是双指针的进阶应用。右边界 right 负责寻找可行解（扩张），左边界 left 负责寻找最优解（收缩）。

思路推演

1. 初始化：left = 0, sum = 0, minLen = 无限大。
2. 移动右边界：遍历数组，将 nums[right] 加入 sum。
3. 判断与收缩：如果 sum >= target，计算当前长度并更新 minLen。随后尝试移除 nums[left] 并右移 left，直到 sum < target。
4. 返回结果：若 minLen 未更新，返回 0。

避坑指南

• 陷阱一：使用 if 代替 while 会导致漏掉最优解。必须用 while 循环持续收缩直到不满足条件。
• 陷阱二：minLen 初始化为 INT_MAX，而非 0。
• 陷阱三：虽然嵌套循环，但每个元素进出窗口各一次，总复杂度为 O(n)。

---

2、3 无重复字符的最长子串

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。