算法 | 滑动窗口

概念

滑动窗口是一种常用的算法技巧，用于处理数组或字符串中的子序列或子串问题。它通过维护一个固定大小的窗口来解决这类问题。
滑动窗口算法通常使用两个指针，分别表示窗口的左边界和右边界。初始时，窗口的大小为0，左右边界都指向数组或字符串的起始位置。
然后，根据具体问题的要求，通过移动右边界或左边界来调整窗口的大小。在每次窗口大小发生变化时，我们可以根据题目要求进行相应操作，比如记录最大值、更新结果等。

移动窗口的规则通常有以下几种情况：

1. 扩大窗口：右边界向右移动，扩大窗口的大小。
2. 缩小窗口：左边界向右移动，缩小窗口的大小。
3. 判断窗口是否有效：根据题目要求判断窗口内的元素是否满足条件。
4. 更新结果：根据题目要求更新结果，如记录最大值、计算子串长度等。

滑动窗口算法的核心思想是利用窗口的增减过程，避免不必要的重复计算，从而提高算法的效率。它在处理连续子序列、子串问题时具有较高的效率，并且时间复杂度通常为线性级别。
需要注意的是，滑动窗口算法并不适用于所有问题，它只能解决一些特定类型的问题。在使用滑动窗口算法时，需要根据具体问题的特点进行合理的设计和调整。

例题-无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

题解：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)return 0;
        unordered_set<char> lookup;
        int maxStr=0;
        int left = 0;
        for(int i=0;i<s.size();i++){
            while(lookup.find(s[i])!=lookup.end()){
                lookup.erase(s[left]);
                left++;
            }
            maxStr =max(maxStr,i-left+1);
            lookup.insert(s[i]);

        }
        return maxStr;
    }
};