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

  • 时间复杂度：O (n)

  • 空间复杂度：O (m)

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

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