原题：无重复字符的最长子串

思路：用哈希表记录每个出现过的字符串的下标，滑动窗口表示当前子串

思路

遍历每个字符

  1. 如果哈希表中已有该字符串，且在窗口范围中 hashMap.has(char) && hashMap.get(char) >= left，更新滑动窗口起点

  2. 如果没有该字符串，则计算当前下标（即窗口的终点）到起点 left 的长度，与最大值 max 比较，保留较大的值

  3. 每次循环的最后记录当前字符的下标 hashMap.set(char, right)

1. 初始化

1
2
3
4
// 哈希表
const hashMap = new Map();
// 最大子串长度
let max = 0;

开始遍历，滑动窗口起点 **left = -1 (重点)**，计算长度时公式为 right - left，不算入 left 上的字符
此时若计算下标 right = 0 的子串长度，结果为 left - right 即 0 - (-1) = 1

1
2
3
for (let right = 0, left = -1; right < s.length; right++) {
  ...
}

2. 检查哈希表

如果 left 到当前下标之间有重复字符，设置滑动窗口为重复字符的下标

1
2
3
4
// 如果 left 到当前下标之间有重复字符
if (hashMap.has(char) && hashMap.get(char) >= left)
  // 设置子串起点为重复的字符下标
  left = hashMap.get(char);

3. 更新最大值

如果没有重复字符，更新最大值，值为 right - left，不包括 left 上的字符

1
2
// 如果没有重复才更新最大值，长度为 left 到 i，不包括 left 上的字符
else max = Math.max(right - left, max);

4. 记录当前字符下标

1
hashMap.set(char, right);

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  // 哈希表
  const hashMap = new Map();
  // 最大子串长度
  let max = 0;
  // 遍历字符串，子串起点设为 -1
  for (let right = 0, left = -1; right < s.length; right++) {
    const char = s.charAt(right);
    // 如果 left 到当前下标之间有重复字符
    if (hashMap.has(char) && hashMap.get(char) >= left)
      // 设置子串起点为重复的字符下标
      left = hashMap.get(char);
    // 如果没有重复才更新最大值，长度为 left 到 rigth，不包括 left 上的字符
    else max = Math.max(right - left, max);
    // 记录当前字符下标
    hashMap.set(char, right);
  }
  return max;
};