刷题_无重复字符的最长子串

发表于2024-04-08更新于2025-09-28阅读次数

内容

原题名叫做：无重复字符的最长子串。给定一个字符串，找出其中不含有重复字符的最长子串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

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

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

提示：
0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

分析

要判断

代码

解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
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        typedef std::unordered_map<char, int> CharIntMap;
        CharIntMap charIntMap;
        int s_len = s.length();
        int longestLen = 0;
        for (int i = 0; i < s_len; ++i)
        {
            for (int j = i; j < s_len; ++j)
            {
                if (charIntMap[s[j]] == 1)
                {
                    if (j - i > longestLen)
                    {
                        longestLen = j - i;
                    }
                    charIntMap.clear();
                    break;
                }
                else
                {
                    charIntMap[s[j]] = 1;
                    if (j - i > longestLen)
                    {
                        longestLen = j - i;
                        // this is wrong. should update longest
                    }
                }
            }
        }
        return longestLen;
    }
};

坑

如果字符串本来就没有重复的，我们应该也在else中给longest计数，但要注意，应该是j - i + 1与longest比较。

1
2
3
4
5
6
7
8
else
{
    charIntMap[s[j]] = 1;
    if (j - i + 1 > longestLen)
    {
        ++longestLen;
    }
}

效果

虽然正确。但是效率不是特别高，结果如下：

1
2
3
987/987 cases passed (654 ms)
Your runtime beats 5 % of cpp submissions
Your memory usage beats 5.02 % of cpp submissions (148.9 MB)

优化_利用哈希记录的已出现过的字符位置，加速滑动

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(std::string s) {
        typedef std::unordered_map<char, int> CharIntMap;
        CharIntMap charIntMap;
        int s_len = s.length();
        int longestLen = 0;
        for (int i = 0; i < s_len; ++i)
        {
            int j = i;
            if (charIntMap[s[j]] == 1)
            {
                if (j - i > longestLen)
                {
                    longestLen = j - i;
                }
                charIntMap.clear();
                break;
            }
            else
            {
                charIntMap[s[j]] = 1;
                if (j - i > longestLen)
                {
                    longestLen = j - i;
                    // this is wrong. should update longest
                }
            }
        }
        return longestLen;
    }
};

解2_哈希记录已出现过的字符位置，加速滑动

Map表中的value应该存char的标记

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
class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        typedef std::unordered_map<char, int> CharIntMap;
        CharIntMap charIntMap;
        int s_len = s.length();
        int longestLen = 0;
        for (int i = 0; i < s_len; ++i)
        {
            for (int j = i; j < s_len; ++j)
            {
                if (charIntMap[s[j]] == 1)
                {
                    if (j - i > longestLen)
                    {
                        longestLen = j - i;
                    }
                    charIntMap.clear();
                    break;
                }
                else
                {
                    charIntMap[s[j]] = 1;
                    if (j - i > longestLen)
                    {
                        longestLen = j - i;
                        // this is wrong. should update longest
                    }
                }
            }
        }
        return longestLen;
    }
};

心得

这个题目属于

总结