滑动窗口算法详解：最小子数组与无重复字符

滑动窗口算法详解

滑动窗口本质上也是双指针，但与前文介绍的相向移动不同，滑动窗口的两个指针是同向移动的。本文通过两个经典题目介绍滑动窗口的基本使用。

长度最小的子数组

题目描述

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

算法原理

滑动窗口的本质是两个指针同向移动，通过这两个指针的移动判断区间之和是否满足条件。如果满足就进行比较长度大小。

初始化时两个指针起点相同：

int left = 0, right = 0;

滑动窗口涉及两个操作：进窗口和出窗口。

• 进窗口：当区间之和 < target 时，需要更多数字参与，右指针向右移动。
• 出窗口：当区间之和 >= target 时，尝试缩小窗口以寻找更短长度，左指针向右移动。

代码实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ans = INT_MAX, left = 0, right = 0, sum = 0;
        for (; right < nums.size(); right++) {
            sum += nums[right];
            while (sum >= target) {
                ans = min(ans, right - left + 1);
                sum -= nums[left++];
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

无重复字符的最长子串

题目描述

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

算法原理

本题同样适用滑动窗口三部曲：第一是进窗口，第二是判断，第三是出窗口。 使用哈希映射（数组模拟）来判断是否存在重复字符。如果映射值大于 1，则说明有重复，需要出窗口直到满足条件。

代码实现

class Solution {
public:
    {
         hash[] = {}, ans = ;
         ( left = , right = ; right < s.(); right++) {
            hash[s[right]]++;
             (hash[s[right]] > ) {
                hash[s[left++]]--;
            }
            ans = (ans, right - left + );
        }
         ans;
    }
};