滑动窗口入门

Leetcode 3.题目如下：

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

实例：

输入: s = "abcabcbb"

输出: 3

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

题意解读

给你一个字符串S，寻找一个子串T，保证T里面的字符都是唯一的。

题解

那么我们该如何思考这个问题呢？

既然是一个类型的题目，我们首先来了解下滑动窗口的2个概念：

滑动：指一个区间往一个方向进行移动，本题中使用从左到右的方式进行滑动。

窗口：也就是一个区间，这个区间可能会增大，也可能会缩小，也可能是固定的。在本题中，我们可以使用队列来表示窗口，这个队列可大可小，要求其最大值。

但是光有这两个概念根本解决不了本题，我们还缺什么呢？

是的，是窗口要如何变化，如何变大或者缩小。这是问题的核心。

对于字符串abcabcbb，一开始肯定是将a放到队列中，接着放入b，每次放入字符的时候，我们都要检查队列里面有没有相同的字符。显然，光有滑动窗口是不够的，我们还需要一个数据结构来记录队列里面是否存在某个字符，于是我们加入辅助的结构set。

如果每次放入一个字母，我们就看set中有没有，如果没有，那么我们可以直接放；如果存在，我们需要先找到之前的字母位置，并且把这个字母连带它前面的字符都出队列，这样我们才能放入新的字母。

核心点

1 采用set记录是否重复。

2 重复了要删除前字母，删除前字母会将窗口左边界右移。

3 新字母会让窗口右边界右移一位。

C++代码

class Solution {
public:
    int lengthOfLongestSubstring(string s)
    {
        if (s.size() == 0)
            return 0;
        unordered_set<char> hash;
        int m = 0;
        int left = 0;

        for (int i = 0; i < s.size(); i++) {
            // 存在就删除到存在的元素处
            while (hash.find(s[i]) != hash.end()) {
                hash.erase(s[left]);
                left++;
            }

            // 更新最长区间
            m = max(m, i - left + 1);
            // 插入新元素
            hash.insert(s[i]);
        }

        return m;
    }
};