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

难度:🟡 中等

标签哈希表字符串滑动窗口

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

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

核心思想

本题的目标是找到一个最长的、不包含重复字符的连续子串。解决这个问题的核心在于如何高效地维护和更新一个“当前没有重复字符”的子串,并记录其最大长度。

思路选择

滑动窗口法 是解决此问题的标准最优思路。

  • 我们使用两个指针,leftright,来定义一个“窗口”,这个窗口内的子串是我们当前正在考察的无重复字符的子串。

  • right 指针负责向右扩展窗口,left 指针则在窗口内出现重复字符时向右收缩。

  • 为了能快速判断一个字符是否在当前窗口内出现过,并找到它上次出现的位置,我们使用一个 哈希表(Map) 来存储窗口内每个字符及其最新的索引。

关键步骤

  1. 初始化:初始化左指针 left = 0,最大长度 maxLength = 0。创建一个哈希表 map 用于存储字符和它们的索引。

  2. 循环遍历:用右指针 right 从 0 开始遍历整个字符串 s

  3. 检查重复与收缩窗口: a. 对于当前字符 s[right],检查它是否已存在于 map 中。 b. 如果存在,并且它上一次出现的位置 map.get(s[right]) 大于等于当前窗口的左边界 left,说明该字符在当前窗口内重复了。我们需要收缩窗口,将左指针 left 移动到重复字符的下一个位置,即 left = map.get(s[right]) + 1

  4. 扩展窗口与更新: a. 无论是否重复,都更新 map 中当前字符 s[right] 的索引为最新的位置 right。 b. 计算当前窗口的长度 right - left + 1,并用它来更新 maxLength

  5. 返回结果:遍历结束后,maxLength 就是最终答案。

代码实现

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    let left = 0, maxCount = 0, result = 0;
    let map = new Map();

    for (let right = 0; right < s.length; right++) {
        // 如果发现重复字符
        if (map.has(s[right])) {
            // 更新左边界,注意要取 max 防止左边界回退
            left = Math.max(left, map.get(s[right]) + 1);
        }
        // 更新字符的最新位置
        map.set(s[right], right);
        // 计算当前窗口长度
        maxCount = right - left + 1;
        // 更新全局最大长度
        result = Math.max(result, maxCount);
    }
    return result;
};

复杂度分析

  • 时间复杂度O(n) 其中 n 是字符串 s 的长度。我们只需要对字符串进行一次完整的遍历,leftright 指针都只向前移动。

  • 空间复杂度O(min(m, n)) 其中 n 是字符串长度,m 是字符集的大小(例如 ASCII 码为 128)。空间消耗取决于哈希表中存储的不同字符的数量,最多为 min(m, n)

相关题目

总结

本题是滑动窗口算法的经典入门题。其核心在于理解如何通过双指针和哈希表来维护一个动态的、符合条件的“窗口”,并在遍历过程中不断更新最优解。这个模型在解决各类子串/子数组问题时非常强大。

Copyright © Jun 2025 all right reserved,powered by Gitbook该文件修订时间: 2025-07-03 17:35:08

results matching ""

    No results matching ""

    results matching ""

      No results matching ""