美文网首页
#3 Longest Substring Without Rep

#3 Longest Substring Without Rep

作者: KedAyA | 来源:发表于2017-02-21 15:40 被阅读7次

寻找字符串中无重复字母的最长字串,使用2个指针移动,当右指针找到hash表中重复的字幕时,讲左指针移动到表中记录位置的下一位,并更新表中数据为右指针位置,更新最大长度,复杂度为O(n)

var lengthOfLongestSubstring = function(s) {
    var longest = 0,p1 = 0,p2 = 0,len = s.length,hash = {};
    if(len === 1)
        return 1;
    while (p2 < len) {
        if (hash[s[p2]] !== undefined) {
            longest = Math.max(longest, p2-p1);
            p1 = Math.max(hash[s[p2]] + 1, p1);
        }
        hash[s[p2]] = p2++;
    }
    if(longest === 0) {
        return len;
    }
    longest = Math.max(longest, len - p1);
    return longest;
};

相关文章

网友评论

      本文标题:#3 Longest Substring Without Rep

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