通过字典 & 双指针滑动窗口实现

  • 时间复杂度:O (n)
  • 空间复杂度:O (m)

    1. function lengthOfLongestSubstring(str) {
    2. let p1 = 0;
    3. let length = 0;
    4. const map = new Map();
    5. for (let p2 = 0; p2 < str.length; p2++) {
    6. const item = str[p2];
    7. if (map.has(item) && map.get(item) >= p1) {
    8. p1 = map.get(item) + 1;
    9. }
    10. length = Math.max(length, p2 - p1 + 1);
    11. map.set(item, p2);
    12. }
    13. return length;
    14. }

上方代码中只有一个 for 循环,所以时间复杂度是 O (n)n 就是字符串的长度。代码中有个 map 字典,主要存储字符串中不重复的字符,所以空间复杂度是 O (m)m 是字符串中不重复字符的个数。