首页 > 代码库 > Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

2024-07-04 14:46:51   222人阅读

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路：本题找出字符串中最长的不包含相同的字符的子字符串不包含相同的字符。可以使用hash表来解决这道题。主要思路就是使用两个头尾指针，尾指针不断往后搜索，当该字符在前面出现过了，记录字符的长度和最长结果，此时头指针不断往后搜索，同时记录的长度count要减一，直到头指针指向的字符与尾指针相同时结束搜索，同时头指针向后移动一位，记录访问过的字符，长度count加一。最后优化最长结果。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n=s.size();
        if(n<=1)
            return n;
        int result=0;
        int count=0;
        int begin=0;
        vector<bool> charTable(256,false);
        for(int i=0;i<n;i++)
        {
            if(charTable[s[i]]==false)//前面字符没有出现过，false表示没有出现过。
            {
                charTable[s[i]]=true;
                count++;
            }
            else
            {
                result=max(result,count);
                while(true)
                {
                    charTable[s[begin]]=false;
                    count--;
                    if(s[begin]==s[i])
                        break;
                    begin++;
                }
                begin++;
                charTable[s[i]]=true;
                count++;
            }
        }
        result=max(result,count);
        return result;
    }
};

 　　这道题也可以使用STL中的hash_map解决。至于如何实现，待我熟悉hash_map便可进行。


联系
我们