【LeetCode 3】 无重复字符的最长子串

题目链接

Problem Description

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

示例 1:

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

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

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

思路

这道题如果用暴力的话时间复杂度是O(n^2)，所以我们需要想办法进行优化，怎么优化呢？

因为暴力中有很多操作是多余的，比如遇到相同的字符时就没必要再执行下去了，因此我们就需要从这个地方下手，

利用双指针滑动窗口，维护窗口中不允许有重复的字符出现，一旦有重复字符，就更新窗口，让窗口的begin指针前移，知道窗口中没有重复字符为止，

下面以abcabcbb作为示例进行演示：（期间还需要一个数组flag，用于记录某个字符是否出现过）

最开始的时候begin指针和i指针都在字符串的起始位置

然后i指针不断前移，直到走到这里，发现flag[a]为1，a出现过，此时就需要更新begin指针

将begin指针移动到<begin，i>这个窗口中没有重复字符，然后 i 继续++，需要更新begin指针时，继续更新窗口

下面结合代码再捋一遍

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() < 2){
            return s.length();
        }
        int flag[128] = {0};//用于存滑动窗口内字符出现的次数，以便更新窗口
        int begin = 0;//双指针滑动窗口
        int ans = 0;
        for(int i = 0; i < s.length(); i++){
            if(flag[s[i]] >= 1){  //说明字符s[i]出现过，此时需要更新滑动窗口的begin指针
                while(flag[s[i]]){  //begin更新到窗口内没有重复字符的地方
                    flag[s[begin]]--;
                    begin++;
                }
            }
            flag[s[i]]++;//标记字符
            ans = max(ans,i-begin+1);
        }
        return ans;
    }
};