无重复字符的最长子串

题目描述

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

输入输出样例

Input: s = "abcabcbb"
Output: 3

  因为无重复，所以最后的b需要被舍去。因此最长子串是"abc"，所以其长度为3

题解

  这道题目我们可以使用滑动窗口的做法，从而避免使用暴力解法所导致的$O(n^{2})$的空间复杂度。滑动窗口其实主要就是使用双指针中的左右指针的技法。
  初始化left = right = 0，把索引左闭右开的区间[left,right)称为一个「窗口」。我们先不断增加right指针扩大窗口[left,right],对应的键值也会增加，直到键值大于1时。此时，我们停止增加right,转而不断增加left指针缩小窗口,从而找到真正的不重复的子串。具体代码如下

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> windows;

        int left = 0,right = 0;
        int res = 0; // 用于记录结果

        while (right < s.size()) {
            //C是将要移入窗口的字符
            char c = s[right];
            right++;
            // 更新数据
            windows[c]++;
            // 判断窗口是否需要收缩
            while (windows[c] > 1) {
                char d  = s[left];
                left++;
                windows[d]--;
            }

            res = max(res,right-left);
        }
        return res;
    }
};