每天一道力扣题:3. 无重复字符的最长子串

191 阅读3分钟

题目

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

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


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


思路

这道题的Tag属于滑动窗口(sliding window)。滑动窗口是字符串或者数组中常见的一种抽象概念,窗口指的是在数组或者字符串中由开始索引、结束索引所组成的一系列元素的集合([i, j) 左闭右开)。而滑动指的是窗口的边界i 、j可以左右移动。比如如果窗口往右移动1位,则变成[i+1, j+1)。

滑动窗口

使用Set作为滑动窗口。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const size = s.length
    if (!size) return s
    const subStrSet = new Set() // 存储窗口的元素,用于快速判重
    let i = 0 // 滑动窗口左边界
    let j = 0 // 滑动窗口右边界
    let len = 0 // 最长子串长度

    // 遍历字符串、移动窗口
    while(i < size && j < size) {
        if (!subStrSet.has(s[j])) {
            // 当字符没有存在set,则push进去
            // 同时需要移动滑动窗口右边界、更新最长子串长度
            subStrSet.add(s[j++])
            len = Math.max(len, j-i) // 这里取len与j-i最大,其实就是利用len缓存之前出现过的最大值
        } else {
            // 如果已存在,出现重复字符
            // 从set删除重复字符前面的字符串,移动滑动窗口左边界
            // 这里j不变也是一个关键,下次还是扫描到重复元素s[j]
            subStrSet.delete(s[i++])
        }
    }
    return len
};

时间复杂度:O(n),最坏情况时间复杂度是O(2n),每个字符都恰好被i,j访问一次。 空间复杂度: O(min(m, n)),空间复杂度主要由Set大小决定,而Set大小其实就是取决于字符串大小n、字符集/字母的m。即0~n之间。

进阶版滑动窗口

上一个版本时间复杂度最坏情况下是O(2n),每个字符恰好被i、j访问一次。只所以出现这个问题是因为之前如果一个元素s[k]出现在窗口[i, j)之间,我们会不断从Set删除前面元素,并通过i++来进行缓慢的左边界移动导致元素被重复访问。

优化版就是解决上述问题,也就是说,如果s[k]在窗口[i, j)之间出现重复元素k`,那么我们直接跳过[i, k ],把i变成k+1。

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const size = s.length
    if (!size) return s
    const indexMap = new Map() // 存储字符元素与索引位置的映射
    let len = 0 // 最长子串长度

    // 遍历字段s
    // i: 窗口左边界值
    // j: 窗口右边届值
    for (let i = 0, j = 0; j < size; j++) {
        if (indexMap.has(s[j])) {
            // 如果之前出现了重复元素s[i],直接移动窗口左边界i到上一个s[i]元素对应索引位置
            i = Math.max(indexMap.get(s[j]), i)
        }
        len = Math.max(len, j - i + 1) // 这里取len与j-i+1最大,其实就是利用len缓存之前出现过的最大值
        indexMap.set(s[j], j + 1) // 这里存的是s[j]与对应索引+1的映射关系,主要方便后面修改i
    }
    return len
};

时间复杂度O(n)。 空间复杂度O(min(m,n)),m是字符集大小,n是字符大小。

以下动图来源于网络。

gifhome_1158x798.gif

广告位

觉得有意思点个右下角在看,或者直接关注。

qrcode_for_gh_1f177110559d_430.jpg