滑动窗口实战：长度最小的子数组与无重复字符的最长子串

滑动窗口算法实战

本文针对两个经典的滑动窗口问题展开解析：长度最小的子数组和无重复字符的最长子串。通过对比暴力解法，展示双指针不回退策略如何将时间复杂度优化至 O(N)。

1. 长度最小的子数组

题目链接： 209. 长度最小的子数组 - LeetCode

问题分析

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

解法思路

暴力枚举所有子数组的时间复杂度为 O(N²)，在数据量较大时会超时。我们可以利用滑动窗口的思想来优化。

维护一个窗口 [left, right]，不断向右移动右指针 right 扩大窗口，累加窗口内元素和 sum。当 sum >= target 时，记录当前窗口长度，并尝试移动左指针 left 缩小窗口，直到 sum < target。在这个过程中，我们不需要回溯 left 指针，因为对于当前的 right，一旦找到满足条件的最小 left，下一个 right 对应的最优 left 一定在当前 left 的右侧或相同位置。

C++ 代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), sum = 0, len = INT_MAX;
        for (int left = 0, right = 0; right < n; right++) {
            sum += nums[right]; // 右指针进窗口
            while (sum >= target) { // 满足条件，尝试收缩左边界
                len = min(len, right - left + 1);
                sum -= nums[left++]; // 左指针出窗口
            }
        }
        return len == INT_MAX ? 0 : len;
    }
};

复杂度分析

• O(N)。虽然有两层循环结构，但 和 指针都只向右移动，每个元素最多被访问两次。