滑动窗口问题

前言

滑动窗口是一类特殊的双指针类型题，只不过他的双指针是同向移动。
滑动窗口和双指针最大的区别是，滑动窗口更关心窗口内的值，而不只两个指针上的元素。
使用滑动窗口解决的问题通常是暴力解法的优化。
很多时候滑动窗口会和哈希表一起使用。

一、无重复字符的最长子串（中）

题目

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

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

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

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

提示：
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

题解

对于数组或字符串寻找找最xx这一类的，都可以用滑动窗口法
1、那什么是滑动窗口呢
其实就是一个队列。比如abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当窗口右移进入a，队列变成了abca，这时候不满足要求。所以，我们要移动这个队列！
2、如何移动
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
3、具体操作
使用unordered_set作为容器，unordered_set是无序且只有唯一值的容器；
unordered_set.insert是在头部插入，当插入元素已存在容器中时，默认删除容器中的元素，按插入的元素排列

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()) {
        // 找到有相同的字母,窗口右移
        // 用while是因为可能有连续多个相同的字母
        lookup.erase(s[left]);
        left++;
      }
      maxStr = max(maxStr, i - left + 1);
      lookup.insert(s[i]);
    }
    return maxStr;
  }
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

请作者喝杯咖啡吧