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

滑动窗口算法实战

滑动窗口是处理连续区间问题的核心技巧，通过维护一个动态的左右指针区间，可以在 O(N) 的时间复杂度内解决许多暴力解法无法承受的问题。本文将深入剖析两道经典题目，展示如何运用双指针优化算法效率。

题目一：长度最小的子数组

问题描述

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

解题思路

暴力求解

枚举所有可能的起始位置，向后寻找满足条件的最短区间。这种方法需要两层循环，时间复杂度为 O(N^2)，在数据量较大时容易超时。

滑动窗口优化

由于我们需要寻找的是连续区间，且随着右指针的移动，左指针通常不需要回退，这符合滑动窗口的特征。

1. 初始化：定义 left 和 right 指针均指向数组头部，sum 记录当前窗口内的元素和，len 记录最小长度（初始化为最大值）。
2. 扩张窗口：移动 right 指针，将元素加入 sum。
3. 收缩窗口：当 sum >= target 时，说明当前窗口满足条件。此时更新 len，然后尝试移动 left 指针缩小窗口，同时从 sum 中减去移出的元素。只要 sum 仍满足条件，就继续收缩，以找到以当前 right 结尾的最短子数组。
4. 结束：遍历结束后，若 len 未被更新则返回 0，否则返回 len。

为什么能降低复杂度？ 虽然代码中有嵌套循环的结构，但 left 和 right 指针都只向右移动，每个元素最多被访问两次（一次进入窗口，一次离开）。因此总的时间复杂度降为 O(N)。

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 + ); 
                sum -= nums[left++]; 
            }
        }
         len == INT_MAX ?  : len;
    }
};