LeetCode_3:无重复的最长子串

发表于 更新于 分类于 ， Waline： 阅读次数：

题目

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2:

Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3:

Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//暴力法
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0) return 0;
        int tmp=1;
        for(int i=0;i<s.length();i++){
            for(int j=i+1;j<s.length();j++){
                if(s.substr(i,j-i).find(s[j])==std::string::npos)
                {
                    tmp=(tmp>j-i+1)?tmp:j-i+1;
                }else{
                    break;
                }
            }
        }
        return tmp;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//滑动窗口法
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0) return 0;
        set<char> se;
        int tmp=0;
        int i=0,j=0;
        while(i<s.length()&&j<s.length()){
            if(se.find(s[j])==se.end()){
                se.emplace(s[j++]);
                tmp=(tmp>j-i)?tmp:j-i;
            }else{
                se.erase(s[i++]);
            }
        }
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//优化的滑动窗口
//c++中map的insert和emplace方法都是无则插入，有则不动
/*我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说，如果 s[j]在[i, j)范围内有与 j'重复的字符，我们不需要逐渐增加i。我们可以直接跳过 [i，j']范围内的所有元素，并将 i 变为 j' + 1 */
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i=0,j=0,ans=0;
        map<char,int> m;
        while(j<s.length())
        {
            if(m.find(s[j])!=m.end()){
                i=max(i,m[s[j]]);
            }
            ans=max(ans,j-i+1);
            m[s[j]]=j+1;
            j++;
        }
        return ans;
    }
};

说明

  • C++的暴力法不一定超时，但是也需要超长的时间不推荐