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

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

滑动窗口是处理连续区间问题的常用技巧。本文将通过两道经典题目，深入剖析其核心逻辑与 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++ 代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0}; // 数组模拟哈希表
        int left = 0, right = 0, ret = 0;
        int n = s.size();
        while (right < n) {
            hash[s[right]]++; // 字符入窗
            while (hash[s[right]] > 1) { // 有重复，收缩左边界
                hash[s[left++]]--;
            }
            ret = max(ret, right - left + 1); // 更新结果
            right++;
        }
        return ret;
    }
};

这两道题展示了滑动窗口在不同场景下的变体：前者基于数值和判断，后者基于字符频次。掌握这一模式能显著提升处理区间类问题的效率。