leetcode

中等哈希表字符串滑动窗口

方法1 暴力解法

var lengthOfLongestSubstring = function(s) {
  const len = s.length, set = new Set();
  let ans = 0;
  for (let i = 0; i < len; i++) { // start
    for (let j = i; j < len; j++) { // end
      const char = s.charAt(j);
      if (!set.has(char)) {
        set.add(char);
        continue;
      } else {
        ans = ans > set.size ? ans : set.size;
        set.clear();
        break;
      }
    }
  }
  ans = ans > set.size ? ans : set.size;
  return ans;
};

1. 准备一个哈希表，用于存放 strArr[i] 到 strArr[j] 的所有成员
2. 准备一个存放结果的变量 ans
3. 遍历数组，i 指向当前成员，每次遍历，j 都从 i 出发向右移动，直到 strArr[j+1] 和哈希表中的成员重复
4. 比较大小：「当前哈希表的长度」和「ans」，确保 ans 中存放的是较大的值
5. 清空哈希表，继续遍历下一项
6. 遍历结束后，再次执行 4

方法2 滑动窗口

var lengthOfLongestSubstring = function(s) {
  const len = s.length, set = new Set();
  let ans = 0, end = -1;
  for (let i = 0; i < len; i++) { // 收缩窗口
    if (i !== 0) set.delete(s.charAt(i - 1));
    while (end + 1 < len && !set.has(s.charAt(end + 1))) { // 扩展窗口
      set.add(s.charAt(end + 1));
      end++;
    }
    ans = Math.max(ans, set.size);
  }
  return ans;
};

收缩窗口：start 移动，start 扫过的区域，全部都从 set 集合中移除，delete。
扩展窗口：end 移动，end 扫过的区域，全部都丢到 set 集合中，add。

和方法1非常类似，不同点在于 end 指针的移动不再是从 start 开始，而是基于上一次的位置开始。

**end = -1**、end 的移动逻辑
end 移动时，意味着扩展窗口。但是 end 每次移动之前，需要处理的逻辑：

1. 判断下一个位置是否还有成员，如果没有，则不移动；否则进入下一步。
2. 判断下一个位置的成员是否已经在哈希表中存在，若存在，则不移动；否则进入下一步。
3. 将下一个成员加入到哈希表中
4. 重复以上步骤

end 开始赋值为 -1，也是为了让代码更优雅，好从字符串下标 0 的位置开始判断。