通过字典 & 双指针滑动窗口实现
- 时间复杂度:O (n)
空间复杂度:O (m)
function lengthOfLongestSubstring(str) {
let p1 = 0;
let length = 0;
const map = new Map();
for (let p2 = 0; p2 < str.length; p2++) {
const item = str[p2];
if (map.has(item) && map.get(item) >= p1) {
p1 = map.get(item) + 1;
}
length = Math.max(length, p2 - p1 + 1);
map.set(item, p2);
}
return length;
}
上方代码中只有一个 for 循环,所以时间复杂度是 O (n),n 就是字符串的长度。代码中有个 map 字典,主要存储字符串中不重复的字符,所以空间复杂度是 O (m),m 是字符串中不重复字符的个数。