LeetCode in JavaScript#3 Longest

LeetCode Longest Substring Without Repeating Characters

Solution

使用两个变量记录子串的头尾位置
当前位置即为子串尾位置
无重复字符子串长度 = 当前位置 - (当前位置字符上次出现位置 + 1) + 1
一种方法是一步一步的将头移动到当前位置字符上次出现的位置+1 但这样会有多余的操作
更好的方法是使用哈希表记录字符上次出现的位置 直接将头移动到该位置

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

时间复杂度 O(n)
空间复杂度 O(m) m为字符串中不同字符的数量