无重复字符的最长子串

发表于

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
简单分析：
假设给出一个字符串： abcdechjil
第一个重复字符是c, 然而如果是简单暴力的话， 第一次从a开始找，找到第一个重复字符c，break，然后下一次要从b开始找
但是发现一个问题，因为b在 c的左边， 所以无论怎么样 无重复字符最长字串长度 都不会大于 从a开始遍历的长度。
所以，下一次直接从重复字符c的下一个字符d开始遍历就ok。

1
2
3
4
5
//暴力伪代码
for (int i = 0; i < n； i++)
{   
    for (int j = i + 1; j < n; j++)  
}

1.没用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 1) return 1;
        map<char,int> m;
        int n = s.size();
        int maxx = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {  
            if (m.find(s[i]) != m.end()) {                                  //找到了
                int id = m[s[i]];
                for (int z = j; z < id; z++) {
                    m.erase(s[z]);
                }
                maxx = max(maxx, i - j);
                j = id + 1;
                // flag = 1;
            } else {
                maxx = max(maxx, i - j + 1);
            }
            m[s[i]] = i;
        }
        return maxx;
    }
};

2.用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        queue<int> q;
        map<char, int> m;
        int maxx = 0;
        for (int i = 0; i < s.size(); i++) {
            if (m.find(s[i]) == m.end()) {
                q.push(s[i]);
                m[s[i]] = 1;
                int size = q.size();
                maxx = max(maxx, size);
            } else {
                while (!q.empty() && q.front() != s[i]) {
                    char c = q.front();
                    q.pop();
                    m.erase(c);
                }
                q.pop();
                q.push(s[i]);
            }
        }
        return maxx;
        
    }
};