剑指 Offer 48. 最长不含重复字符的子字符串

题目

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

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

解法一：暴力法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int size = s.size();
        if(size == 0)return 0;

        int m=0;
        for(int l = 0;l<size;l++){
            unordered_set<char> st;
            st.insert(s[l]);
            int r = l+1;
           
            while(r<size){
                if(st.find(s[r]) != st.end()) break;
                st.insert(s[r]);
                r++;
            }
            m = max(m,r-l);
        }

        return m;

    }
};

结果，果然也很暴力

执行用时：
732 ms
, 在所有 C++ 提交中击败了
5.09%
的用户
内存消耗：
238.3 MB
, 在所有 C++ 提交中击败了
4.99%
的用户
通过测试用例：
987 / 987

优化一下，如果右指针能到s尾部，直接跳出

1	if(r == size-1)break;

结果，好的，更久了靠

执行用时：
872 ms
, 在所有 C++ 提交中击败了
5.09%
的用户
内存消耗：
237.2 MB
, 在所有 C++ 提交中击败了
4.99%
的用户
通过测试用例：
987 / 987

看来得另谋他路了

想到一个思路，有点类似km算法，比如出现123456356时

指针移动到1 2 3 4 5 6 3处发现出现了重复，此时记录最大长度是 6，通常情况下下一次左指针是移动一个单位，此处考虑左指针不移动到1 2 ，而是直接跨越移动，即移动到1 2 3 4

实现：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int size = s.size();
        if(size == 0)return 0;
         if(size == 1)return 1;
        unordered_map<char,int> st;
        int m=0;
        int r = 0;
       
        for(int l = 0;l<size;){
            cout<<"正在开始"<<s[l]<<endl;
            //if(l>0)st[s[l-1]] = 0;
            st[s[l]] = l+1;
            if(r==l) r =l+1;
            int flag = 0;
            while(r<size){
                cout<<st[s[r]]<<" "<<s[r]<<endl;
                if(st[s[r]]!=0) {
                    cout<<"移动指针到"<<s[st[s[r]]]<<endl;
                    m = max(m,r-l);
                    cout<<"max"<<m<<endl;
                    l=st[s[r]];
                    st[s[r]] =r+1;
                    
                    r++;               
                    flag = 1;
                    break;
                }
                st[s[r]]=r+1;
                r++;
            }
            if(flag == 0){l++;}
            
          //  if(r == size-1)break;    
        }

        return m;

    }
};

改到绝望！

喔，发现有个大佬，用一句很简单的话概括了

用一个双端队列当成滑动窗口，当遇到队列中已经存在的数，就从队头开始删(直到删除这个存在的数)，否则就从队尾添加元素

大佬写法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {

        int size = s.size();
        if(size == 0)return 0;
        int res;

        unordered_set<char> st;
        for(int l = 0,r = 0;r<size;r++){
            char current = s[r];
            while(st.find(current) != st.end()){
                st.erase(s[l++]);
            }

            st.insert(s[r]);
            res = max(res,r-l+1);      
        }

        return res;

    }
};

效率直接提升10倍

执行用时：
40 ms
, 在所有 C++ 提交中击败了
8.75%
的用户
内存消耗：
10.6 MB
, 在所有 C++ 提交中击败了
21.50%
的用户
通过测试用例：
987 / 987

我是菜鸡，虽然思路差不多，但是….我写了垃圾，垃圾写垃圾！