此文已同步更新至相关仓库的issues区

LC3.无重复字符的最长子串

中等

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

示例 1:

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

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

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

输入: s = ""
输出: 0

题目分析

首先需要明确一点,子串子序列之间的区别。子串在原始字符串或者数组中是一段连续的数据,而子序列不一定是连续的,但是仍需保证数据中的每个元素之间保持着原数据中的相对顺序。

而这题需要确定的是一个子串,也就是要求的是一段连续的且元素不重复的数据长度,并且长度值越大越好。

对于数组类(这里将这个数据结构也算进来了,也就是所谓的字符串)的数据结构我们有常见的两种处理:查找排序(当然,这不是什么客观定义,只是笔者个人对常出现的操作进行的主观归纳)

而这道题,明显是需要对数据进行查找操作。面对查找操作我们常常是需要进行遍历操作的,观察这题,笔者首先想到的逻辑是需要迭代

对于迭代,我们需要确定一个东西:循环不变量

我们需要确定在我们循环的过程中,有什么数据或者说数据域是具备不变、恒成立的性质,这是我们确定具体思路的关键。

如果采用循环的话,我们会想着用暴力遍历,去枚举所有无重复的子串,然后筛除最长的那个子串。但是这样的话我们对每个元素的操作会达到多个N的常数操作,也就是时间复杂度会达到O(N^2),甚至复杂的题会达到O(N^3)O(N^4)...这是非常糟糕的。

那我们就要想如何进行时间复杂度为O(N)的遍历操作。

这个时候就需要我们去了解新的算法,光是空想解题是很难写出优秀、高质量的程序,我们需要去学习更加优秀、聪明的算法。这里就需要了解到的一个思想:滑动窗口(sliding window)

滑动窗口属于双指针思想的一种,所谓双指针并不是我们编程语言中指内存地址的那个指针,而是一种技巧,通过两个变量去动态地对我们访问(或者说遍历)的数据进行标记(不明白的继续往下看,等下会有演示)。

滑动窗口思想之所以如此取名,其实就是双指针在遍历的时候,会形象地成为一个数据域的两个端点,而数据域中的数据往往是我们所需要的数据,就像是一个窗口一样(想象成窗户,通过窗户我们能看到风景,而窗户旁边则是墙,墙后面的风景我们是看不到的,也是不关心的)。在遍历的过程中,两个指针会根据判别不断地移动,像是在数组上不断滑动的窗口。

将滑动窗口的思想和我们刚刚提到的循环不变量结合,我们很快便能确定此题的大体思路,来看看下面的演示:

我们先假设给出的字符串是:"abcabcbb"

然后定义两个指针指向字符串的头部(我们将上面那个箭头命为 right,下面的箭头命为 left)
↓
abcabcbb
↑

开始遍历:
1、right向右移动,发现 [left, right] 这个数据域中没有重复元素,right 继续移动

 ↓
abcabcbb
↑

2、假设此时遍历到第二个 a, 如果此时 right 移动到第二个 a 上的话,[left, right]这个数据域中便会出现不满足条件的数据,即发现有重复子串。
   ↓
abcabcbb
↑

那我们这个时候就要移动我们的 left, 来缩小数据域(或者说窗口),来达到满足条件的子串的目的。为什么不移动 right 呢?因为我们要同时保证数据域尽可能大且没有重复元素的情况。

看到这里是不是对滑动窗口思想有了一定的认识?同时我们可以思考发现,[left, right]其实就是我们的循环不变量,因为它要始终保持着不重复子串的这一性质,所以这也是为什么说确定了循环不变量,我们就能更好地确定我们具体实现的原因。

那么如何确定我们子串中有重复元素呢?这里当然就要借助额外的空间来记录我们出现过的子串呀。这里笔者采用哈希表进行记录,当然读者们可以思考一下如何用数组去记录,只要能建立一个映射关系就好。

以下是笔者拿到此题后形成的分析思路:

yTJjED.png

题解 - 滑动窗口 + Map

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const len = s.length

    if (len < 2) return len

    const cut = new Map()

    let left = 0,
        right = 0
    let ans = 1
    
    while (right < len) {
        // 记录元素出现次数
        cut.set(s[right], (cut.get(s[right])|| 0) + 1)
        if (cut.get(s[right]) === 2) {
            // 判断元素重复
            while (cut.get(s[right]) === 2) {
                cut.set(s[left], cut.get(s[left ++]) - 1)
            }
        }
        // 每次更新最长子串的长度
        ans = Math.max(ans, right - left + 1)
        right ++
    }
    
    return ans
};

题解 - 滑动窗口 + Map 进一步优化,减少 left 移动次数

刚刚我们采用的是遇到重复的,让left不断移动,一点点缩短范围来达到去重的目的。但是我们可不可做到直接跳到重复的那个元素的后面,直接将重复的元素前的区域移除呢,这样可以不用一点点挪动,可以减少对left的操作。

当然是有的,我们只用转变一个思路,讲记录元素出现的次数,变成出现元素的下标位置,这样的话就能在出现重复的时候,立马定位一个重复元素出现的位置,并直接排除重复区间。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const len = s.length

    // 特判
    if (len < 2) return len

    const map = new Map()

    let left = 0,
        right = 0,
        ans = 1

    while (right < len) {
        
        const point = map.get(s[right])
        
        // 如果 point 为 undefined 的话,说明先前并未出现过此元素,所以没有重复
        if (point !== undefined) {
            left = Math.max(left, point + 1)
        }
        // 更新元素出现的位置
        map.set(s[right], right)
        ans = Math.max(ans, right - left + 1)
        right ++
    }

    return ans
};

多嘴一句,为什么我们能这么大胆地直接将重复元素的前面区域(包含重复元素)都排除呢?因为这是一个子串呀,子串是连续的,细品一下吧。