无重复字符的最长子串

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

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	//双指针(i和j)，一个一直向前，直到遇到一样的，另一个向前,不合理，pass
        set<char> temp;
        int max = 1, count = 0;
        if(s == "") return 0;
    
        for(auto i : s)
        {
            count = temp.size();
            temp.insert(i);

            if(max < temp.size())
                max = temp.size();
            if(count == temp.size()){
                temp.clear();
                for(auto i : temp)
                {
                    cout << i << " ";
                }
                temp.insert(i);
            }
            cout << endl << endl;
        }
        for(auto i : temp)
        {
            cout << i << endl;
        }
        return max;
    }
};
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
27
28
29
30
31
32

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //滑动窗口(暴力)O(n) = n^2
        set<char> temp;
        int max = 1, count = 0;
        int i = 0, j = 0;
        if(s == "") return 0;
    
        for(j = 0; j < s.size(); j++)
        {
            for(i = j; i < s.size(); i++)
            {
                count = temp.size();
                temp.insert(s[i]);

                if(max < temp.size())
                    max = temp.size();
                if(count == temp.size()){
                    temp.clear();
                    for(auto m : temp)
                    {
                        cout << m << " ";
                    }
                    break;
                }
                cout << endl << endl;
            }

        }
        for(auto m : temp)
        {
            cout << m << endl;
        }
        return max;
    }
};
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
27
28
29
30
31
32
33
34
35
36
37

思路：
这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    	//滑动窗口O(n) = n
        if(s.size() == 0) return 0;
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        for(int i = 0; i < s.size(); i++){
        	//这里有set的用法，找s[i]在lookup里面是否存在。
            while (lookup.find(s[i]) != lookup.end()){
                //cout << lookup.find(s[i]) << "   " << lookup.end() << endl;
                lookup.erase(s[left]);
                left ++;
            }
            maxStr = max(maxStr,i-left+1);
            lookup.insert(s[i]);
        }
        return maxStr;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22