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

约 5 分钟
文章信息 15 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 美团 阿里巴巴 快手 百度 华为 虾皮 剑指 Offer 剑指 Offer（第 2 版）
标签
字符串 哈希表 滑动窗口 滑动窗口经典题 子数组问题
目录

题目描述

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

image-20241107211629480

题意分析

给定一个字符串，要求找出其中最长的一段连续字符，使这段字符里没有任何重复，返回它的长度。返回的是长度而不是这段字符本身，这一点决定了过程中只需要维护端点，不用真的截取子串。

约束里的信号有两条。第一，题目强调的是子字符串而不是子序列，所选字符必须在原串中挨在一起，这直接决定了可以用两个端点来刻画候选答案。第二，字符集有限，判断「某个字符是否在当前这段里出现过」可以做到常数时间，不需要每次回头重扫。

边界包括空串（答案为 0）、全部字符互不相同（答案为整个长度）、全部字符相同（答案为 1），以及一个更隐蔽的情形：某个重复字符上一次出现的位置已经落在当前这段的左边，此时它对当前这段毫无影响，不该因为它去调整左端点。

解法：滑动窗口记录最近位置

核心思路

暴力枚举每个起点，再向右寻找第一个重复字符，会反复扫描相同区间，最坏需要 $O(n^2)$。题目要求连续子串，而「窗口内没有重复字符」具有单调性，因此适合滑动窗口。

维护 last[c] 表示字符 c 最近一次出现的位置，并保持不变量：每轮更新答案前，窗口 [left, right] 内没有重复字符。加入 s[right] 后，只有这个新字符可能破坏不变量：若它上次出现的位置 previous 仍在窗口内，就令 left = previous + 1；否则左边界不动。

更稳妥的统一写法是 left = max(left, previous + 1)。取最大值保证左边界绝不回退，例如 "abba" 扫到最后一个 a 时，它的旧位置 0 已在窗口外，不能把 left 从 2 拉回 1。修复窗口后再更新答案，右端点扫描一次即可。

解题步骤

  1. 初始化左边界 left = 0、答案 ans = 0 和最近位置表 last。
  2. 枚举右边界 right，读取新字符 ch = s[right]。
  3. 若 ch 出现过，用 max(left, last[ch] + 1) 更新左边界，排除窗口内的旧 ch，同时忽略窗口外的旧记录。
  4. 记录 last[ch] = right。此时 [left, right] 恢复为无重复窗口，用其长度更新 ans。
  5. 扫描结束后返回 ans。

以 "abba" 为例：扫描第二个 b 后 left 跳到 2；扫描末尾 a 时，旧 a 在下标 0，max(2, 1) 仍为 2，因此窗口是 "ba"，答案为 2。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0;
        int ans = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (last.containsKey(ch)) {
                left = Math.max(left, last.get(ch) + 1);
            }
            last.put(ch, right);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func lengthOfLongestSubstring(s string) int {
    last := make(map[byte]int)
    left := 0
    ans := 0

    for right := 0; right < len(s); right++ {
        ch := s[right]
        if idx, exists := last[ch]; exists && idx+1 > left {
            left = idx + 1
        }
        last[ch] = right
        if right-left+1 > ans {
            ans = right - left + 1
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n)$。右边界只扫描一次，哈希表查询与更新的均摊时间为 $O(1)$。
  • 空间复杂度：$O(\lvert \Sigma \rvert)$，其中 $\Sigma$ 是字符集；最坏也可写作 $O(n)$。

关键点总结

  • 窗口不变量是 [left, right] 内字符互不重复。
  • 最近位置表让左边界一步跳过重复字符，不需要逐个删除窗口元素。
  • left 必须单调不减，max 正是为了解决旧记录已经离开窗口的情况。
  • 面试时用 "abba" 解释左边界为何不能回退，再说明答案必须在修复窗口后更新。

易错点总结

  • 直接赋值 left = last[ch] + 1 会让左边界回退；应取 max，可用 "abba" 检查。
  • 最近位置必须先读取再覆盖，否则会把当前位置误认为上一次出现的位置。
  • 跳转目标是旧位置的下一格，漏写 +1 后重复字符仍在窗口内。
  • 必须先恢复窗口不变量，再计算 right - left + 1。
  • Go 代码按 byte 处理，符合本题字符范围；若输入允许任意 Unicode 字符，应改为遍历 []rune。

相似题目

题目 难度 考察点
3. 无重复字符的最长子串 中等 完全同题的官方主站版本
159. 至多包含两个不同字符的最长子串 中等 约束放宽为不同字符种类数
340. 至多包含 K 个不同字符的最长子串 中等 种类上限参数化，需要计数收缩
424. 替换后的最长重复字符 中等 允许有限次修改的窗口合法性判定
992. K 个不同整数的子数组 困难 恰好 K 种，需两次窗口作差
LCR 016. 无重复字符的最长子串 中等 剑指系列在新题库中的编号