「每日LeetCode」2020年9月22日

本文最后更新于：2023年3月19日 晚上

剑指 Offer 48. 最长不含重复字符的子字符串

剑指 Offer 48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例  1:

1
2
3
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

  • s.length <= 40000

思路

优化的滑动窗口（哈希表）

我们可以使用哈希表记录每个字符的下一个索引，然后尽量向右移动尾指针来拓展窗口，并更新窗口的最大长度。如果尾指针指向的元素重复，则将头指针直接移动到窗口中重复元素的右侧。
算法
tail 指针向末尾方向移动；
如果尾指针指向的元素存在于哈希表中：
head 指针**跳跃到重复字符的下一位**；
更新哈希表和窗口长度。
作者：z1m
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/tu-jie-hua-dong-chuang-kou-shuang-zhi-zhen-shi-xia/

注意判断map.get(s[end]) >= start时，即点在窗口中时，才是出现重复值。

解答

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) {
  let start = 0,
    end = 0;
  let res = 0;
  const map = new Map();
  while (end < s.length) {
    // 如果哈希表中存在该节点，且取到的下标大于头结点，说明在本窗口中重复了，设置窗口左侧和右侧到重复节点的右边一个位置
    if (map.get(s[end]) >= start) {
      start = map.get(s[end]) + 1;
      map.set(s[end], end);
      // 如果不存在，令当前哈希表中的下标加一，求当前窗口大小，判断是否大于最大大小
    } else {
      map.set(s[end], end);
      res = Math.max(res, end - start + 1);
    }
    end++;
  }
  return res;
};