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为字符串中不同字符的数量