Skip to content

3. Longest Substring Without Repeating Characters

难度:Medium

刷题内容

原题连接

  • https://leetcode.com/problems/longest-substring-without-repeating-characters

内容描述


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 **- 时间复杂度: O(NlgN)*- 空间复杂度: O(N)***

用 map储存 key为字符,value 为这个字符的位置,我们可以维护一个子字符串(无重复字符),记录它的起始位置,遍历 string s 当无法在map中找到字符或者小于子字符串的起始位置,就是没有在这个字符串中出现,反之则字符重复,不过 map查找为 O(lgn),因此总的时间复杂度为O(NlgN)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
    map<int,int> m;
    int beg = 0,length = s.length(),ll = 0,ans = 0;
    for(int i = 0;i < length;++i)
    {
        if(m.find(s[i]) == m.end() || m[s[i]] < beg)
            ll++;
        else
        {
            int pos = m[s[i]];
            ans = max(ll,ans);
            ll = ll - (pos - beg);
            beg = pos + 1;
        }
        m[s[i]] = i;
    }
    ans = max(ans,ll);
    return ans;
    }
};

思路 2 **- 时间复杂度: O(NlgN)*- 空间复杂度: O(1)***

这个思路和上面差不多,用到了一个小窍门,因为储存的是字符,char为8位,因此能储存的最大数为256,这样空间复杂度就为O(1)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int m[256];
    for(int i = 0;i < 256;++i)
        m[i] = -1;
    int beg = 0,length = s.length(),ll = 0,ans = 0;
    for(int i = 0;i < length;++i)
    {
        if(m[s[i]] < beg)
            ll++;
        else
        {
            int pos = m[s[i]];
            ans = max(ll,ans);
            ll = ll - (pos - beg);
            beg = pos + 1;
        }
        m[s[i]] = i;
    }
    ans = max(ans,ll);
    return ans;
    }
};


回到顶部