美文网首页LeetCode
3. Longest Substring Without Rep

3. Longest Substring Without Rep

作者: 闭门造折 | 来源:发表于2018-03-20 17:29 被阅读4次

    Given a string, find the length of the longest substring without repeating characters.
    给定一个字符串,找到最长无相同字符连续子串的长度

    举例:

    对于字符串"abcabcbb",答案为"abc",长度为3.
    对于字符串"bbbbb",答案为"b",长度为1.
    对于字符串"pwwkew",答案为"wke",长度为3.
    注意答案必须为连续子串,pwke为子串,但不是连续子串
    

    拟采用方法:
    创建一个数组,记录每个字符对应最后出现的位置
    维护以第i位为字符串末尾的最长满足条件子字符串
    如果第i位为字符x,x未出现过,则cur++,否则cur=min(cur+1,两个x间距离)

    代码如下:

    class Solution {
    public:
        int min_comp(int a, int b){
            return a > b ? b : a;
        }
        int max_comp(int a, int b){
            return a > b ? a : b;
        }
        int lengthOfLongestSubstring(string s) {
            int len = s.length();
            int cur = 0;
            int max = 0;
            int chara[300] = {0};
            char word;
            for(int i = 0; i < len; i++){
                word = s[i];
                cur = min_comp(cur + 1, i + 1 - chara[word]);
                chara[word] = i + 1;
                max = max_comp(cur, max);
            }
            return max;
        }
    };
    

    此题中不止有小写字母,一开始只考虑了小写字母,开了30位,然后数组溢出了

    相关文章

      网友评论

        本文标题:3. Longest Substring Without Rep

        本文链接:https://www.haomeiwen.com/subject/debbqftx.html