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

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

滑动窗口是处理连续区间问题的常用技巧。本文将通过两道经典题目，深入剖析其核心逻辑与 C++ 实现。

1. 长度最小的子数组 (LeetCode 209)

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

解法一：暴力求解 枚举所有可能的起始位置，向后寻找最短区间。虽然直观，但时间复杂度较高，容易超时。

解法二：滑动窗口 利用双指针维护一个窗口 [left, right]。右指针不断扩展窗口以累加和，一旦和满足条件，左指针收缩窗口以尝试找到更短的长度。关键在于左右指针均不回退，确保时间复杂度为 O(N)。

核心思路 当窗口内元素之和大于等于 target 时，记录当前长度并移动左指针；否则移动右指针。这样避免了重复计算前缀和。

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;
    }
};

2. 无重复字符的最长子串 (LeetCode 3)

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

解法一：暴力求解 枚举每个起点，向后遍历直到出现重复字符。需借助哈希表统计频次。

解法二：滑动窗口 同样使用双指针，但需配合哈希表（或数组）记录字符出现次数。当遇到重复字符时，收缩左指针直到重复消除。

核心思路 右指针进入新字符，若该字符频次超过 1，则持续移除左指针字符直至频次恢复为 1。每次移动后更新最大长度。

C++ 代码实现

  {
:
    {
         hash[] = {}; 
         left = , right = , ret = ;
         n = s.();
         (right < n) {
            hash[s[right]]++; 
             (hash[s[right]] > ) { 
                hash[s[left++]]--;
            }
            ret = (ret, right - left + ); 
            right++;
        }
         ret;
    }
};