滑动窗口算法findLongestSubstring实现代码逐行解释求助

这个实现是典型的左右指针滑动窗口方案，全程只遍历字符串一次，时间复杂度为O(n)，比你自己实现的暴力调整窗口版本效率更高。 #

变量初始化说明 #

function findLongestSubstring(str) {
  let longest = 0; // 全局记录遍历过程中找到的最长无重复子串长度
  let seen = {}; // 哈希表，存储每个字符「最后一次出现位置的下一个下标」，用于快速定位重复时左指针的跳转位置
  let start = 0; // 当前无重复字符窗口的左边界下标

循环遍历（右指针移动逻辑） #

// i是当前窗口的右边界下标，全程只向右移动，不会回退
  for (let i = 0; i < str.length; i++) {
    let char = str[i]; // 取当前右指针指向的字符
    // 判断当前字符是否在[start, i]窗口内出现过
    if (seen[char]) {
      // 若出现过，更新窗口左边界：取「原有左边界」和「该字符上次出现位置的下一位」的较大值
      // 取max是为了避免左边界回退：如果该字符上次出现的位置已经在当前窗口左边，就不需要调整左边界
      start = Math.max(start, seen[char]);
    }
    // 计算当前窗口的长度，更新全局最长长度
    // 加1是因为下标从0开始，比如窗口是0~2，共3个字符，2-0+1=3
    longest = Math.max(longest, i - start + 1);
    // 更新哈希表中当前字符对应的跳转位置：存储i+1，下次遇到重复直接跳转到这个位置即可避开重复
    seen[char] = i + 1;
  }
  return longest;
}

运行示例辅助理解 #

我们用abba这个测试用例走完整流程，你就能清晰看到逻辑：

输入abba：

1. i=0，char='a'：seen中无a记录，longest = max(0, 0-0+1) = 1，seen['a'] = 1
2. i=1，char='b'：seen中无b记录，longest = max(1, 1-0+1) = 2，seen['b'] = 2
3. i=2，char='b'：seen['b']=2，start = max(0,2) = 2，longest = max(2, 2-2+1) = 2，seen['b'] = 3
4. i=3，char='a'：seen['a']=1，start = max(2, 1) = 2（这里就是取max的作用，旧的a位置已经在当前窗口外，不需要调整左边界），longest = max(2, 3-2+1) = 2，seen['a'] =4
   最终返回2，结果正确。

内容的提问来源于stack exchange，提问作者GodOfProgrammers