LeetCode--Longest Substring Without Repeating Characters

发表于 | 分类于 |

题目描述：

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

样例：

1
2
3
Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.
1
2
3
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
1
2
3
4
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.

题意：

给你一个字符串 s，找出最长无重复子串，注意，这里是子串，不是子序列。

思路：

因为是找无重复的子串，那么该怎么找呢？蚊子首先就是要一个个字符依次遍历查找

就比如第一个样例：”abcabcbb”

一个个遍历查找首先会找到：”a”, “b”, “c”，此时的子串为 “abc”，长度为 3；

再往后遍历的时候就会查找到 “a”

这时我们发现已经有一个 “a” 了，因为 “a” 就在之前查找的子串之后，并且替换之后长度未发生改变，那我们将这一个新的 “a” 替换原来的 “a”，此时新的子串为 “bca”，长度为 3；

再往后遍历，查找到了 “b”

同样，我们发现原本的子串中已经有一个 “b” 了，并且 “b” 同样在原本的子串之后，长度也没有发生改变，就将新的位置上的 “b” 替换之前的 “b”，此时新的子串为 “cab”；

之后遍历得到的 “c”，同理，这是子串为 “abc”，长度为 3；

再之后遍历得到的 “b”，我们发现子串中已经有一个 “b” 了，同样操作，我们替换之前的 “b”，并且此时子串为 “bc”，长度为 2；

当遍历到最后一个 “b” 时，一样操作并替换，子串为 “b”，长度为 1；

总结：

在上面的描述过程中，我们可以发现，在查找最长无重复的子串时，就相当于一个滑动窗口，在这个滑动窗口里面的字符，是一定没有重复字符的，而我们在每次遍历替换的时候，都会检查加进来的字符，是否重复：若没有重复，那么直接加进滑动窗口；反之，则更新替换。

下面是我刚刚写过的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int begin = -1;
        unordered_map<int, int> mp;
        for(int i = 0; i < s.size(); ++i){
            if(mp.count(s[i]) && mp[s[i]] > begin){
                begin = mp[s[i]];
            }
            mp[s[i]] = i;
            ans = max(ans, i - begin);
        }
        return ans;
    }
};

Runtime：40ms Memory：16.5MB
faster than 41.34%

康了一下网友的题解，比我的快了两倍的样子，太强啦，ORZ~

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
38
39
40
41
class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int size=s.size();

        int table[256];
        for(int i=0;i<256;i++)
        {
            table[i]=-1;
        }

        int ret=0;
        int currtL=0;
        int currtR=size-1;
        for(int i=0;i<size;i++)
        {
            if(table[s[i]]!=-1)
            {
                int preIdx=table[s[i]];
                if(preIdx>=currtL)
                {
                    int tmp=i-currtL;
                    if(tmp>ret)
                    {
                        ret=tmp;
                    }
                    currtL=preIdx+1;
                    if(size-currtL<=ret){break;}
                }
            }
            table[s[i]]=i;
        }
        if(ret<currtR-currtL+1)
        {
          ret=currtR-currtL+1;
        }
        return ret;
    }
};

Runtime：24ms Memory：14.7MB
faster than 77.12%