菜园前端

Appearance

3. 无重复字符的最长子串 ​

原文题目

给定一个字符串 s 请你找出其中不含有重复字符的最长子串的长度。

https://leetcode.cn/problems/longest-substring-without-repeating-characters/

题目分析 ​

博主个人觉得这道题相对前面两道题会难很多。

题目中最难理解的部分应该就是，“不含有重复字符的最长子串的长度” 这句话了。下面将逐步拆解分析。

子串

假设有一个字符串 pwwkew 它的子串如下：

  • pww + kew = pwwkew

  • pw + wk + ew = pwwkew

  • p + wwkew = pwwkew

有太多种组合了，这边就不一一列举了。其实想说的就是，像 pww kew 这种就是子串了。

不含有重复字符

例如子串 pww 就不符合啦，题目要求子串里面的字母不能重复。

最长子串的长度

其实可以从肉眼上看出来，pwwkew 满足题目要求的最长的子串应该是 wke kew，只要返回他们其中一个的长度即可，长度是 3

题解思路 ​

方式一：滑动窗口算法 ​

可以利用滑动窗口，双指针的算法来实现，只要算出最佳的窗口位置，用 p2 - p1 就能求出窗口长度，即最长子串的长度。

js
const lengthOfLongestSubstring = function (s) {
    const map = new Map()
    let p1 = -1
    let length = 0

    for (let p2 = 0; p2 < s.length; p2++) {
        let val = s[p2]

        if (map.has(val)) {
            p1 = Math.max(map.get(val), p1)
        }

        length = Math.max(p2 - p1, length)
        map.set(val, p2)
    }

    return length
}

lengthOfLongestSubstring('pwwkew')
const lengthOfLongestSubstring = function (s) {
    const map = new Map()
    let p1 = -1
    let length = 0

    for (let p2 = 0; p2 < s.length; p2++) {
        let val = s[p2]

        if (map.has(val)) {
            p1 = Math.max(map.get(val), p1)
        }

        length = Math.max(p2 - p1, length)
        map.set(val, p2)
    }

    return length
}

lengthOfLongestSubstring('pwwkew')

时间复杂度：O(n)

空间复杂度：O(n)

思路分析
  1. 首先定义两个指针 p1 = -1 p2 = 0 此时的滑动窗口范围就是 -1 ~ 0 范围结果就是 p，开始遍历字符串 pwwkew，将 p2 指针逐步 +1
  1. 第一次循环 p2 = 1 ，滑动窗口范围就是 -1 ~ 1 范围结果是 pw
  1. 第二次循环 p2 = 2 ，滑动窗口范围就是 -1 ~ 2 范围结果是 pww

  1. 但是滑动窗口中已经存在 w ，所以 p1 的位置就要调整为已存在元素的下标 +1。滑动窗口中之前的 w 下标为 1，所以 p1 = 1 + 1

  2. 第三次循环 p1 = 2 p3 = 3，滑动窗口范围就是 2 ~ 3 范围结果是 wk

  1. 以此类推，直到 for 循环执行完毕，每次 for 循环的过程中都需要更新滑动窗口的长度，取最大值。

  2. 以上为大致的思路，具体效果因代码实现而微调。

代码分析
  1. 首先创建双指针 p1 p2 用于存储滑动窗口下标。以及 map 数据结构用于存储字符串每个字符的下标。
js
const map = new Map()
let p1 = -1
let length = 0
const map = new Map()
let p1 = -1
let length = 0
  1. 然后遍历字符串 s ，其中 p2 为滑动窗口的末尾下标，p1 则是起始下标。遍历的过程中将当前字符和下标存储到数据结构 map 中。
js
for (let p2 = 0; p2 < s.length; p2++) {
    let val = s[p2]

    map.set(val, p2)
}
for (let p2 = 0; p2 < s.length; p2++) {
    let val = s[p2]

    map.set(val, p2)
}
  1. 每一次遍历中，用 p2 - p1 计算窗口的长度。例如有一个矩形，你想计算它的长度，是不是可以通过右侧的 x 坐标，减去左侧的 x 坐标即可，滑动窗口也是一样的方式。题目中要求求出最大的长度，所以需要配合 Math.max 来实现。
js
length = Math.max(p2 - p1, length)
length = Math.max(p2 - p1, length)
  1. p2 是窗口的末尾下标，而且是通过 for 循环进行 +1，没有其他方式改变它，基本上就是固定的输出 0 ~ 字符串的长度。但是 p1 不同，需要根据条件动态调整位置。当遍历的过程中，遇到重复的字符，则将 p1 的下标调整为数据结构 map 中已存在元素的下标。但是如果 p1 的下标本身就大于 map 中已存在元素的下标，则不需要调整位置。
js
if (map.has(val)) {
    p1 = Math.max(map.get(val), p1)
}
if (map.has(val)) {
    p1 = Math.max(map.get(val), p1)
}

更新时间: