LeetCode 题解 | 3. 无重复字符的最长子串
最新回答
挥写ヽ伱旳故事
2026-10-25 17:48:15
方法一、暴力法：
逐个检查所有的子字符串，看它是否不含有重复的字符。
假设我们有一个函数 boolean allUnique(String substring) ，如果子字符串中的字符都是唯一的，它会返回true，否则会返回 false。 我们可以遍历给定字符串 s 的所有可能的子字符串并调用函数 allUnique。 如果事实证明返回值为true，那么我们将会更新无重复字符子串的最大长度的答案。
执行所有步骤耗去的时间总和为：[公式]
方法二、滑动窗口：
在暴力法中，我们会反复检查一个子字符串是否含有有重复的字符，但这是没有必要的。如果从索引 [公式] 到 [公式] 之间的子字符串 [公式] 已经被检查为没有重复字符。我们只需要检查 [公式] 对应的字符是否已经存在于子字符串 [公式] 中。
使用 HashSet 作为滑动窗口，我们可以用[公式] 的时间来完成对字符是否在当前的子字符串中的检查。
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合，即[公式] （左闭，右开）。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如，我们将 [公式] 向右滑动 11 个元素，则它将变为 [公式] （左闭，右开）。
使用 HashSet 将字符存储在当前窗口[公式]（最初 j=ij=i）中。 然后我们向右侧滑动索引 [公式] ，如果它不在 HashSet 中，我们会继续滑动 [公式] 。直到 [公式] 已经存在于 HashSet 中。此时，我们找到的没有重复字符的最长子字符串将会以索引 [公式] 开头。如果我们对所有的 [公式] 这样做，就可以得到答案。
执行所有步骤耗去的时间总和为：[公式]
方法三、优化的滑动窗口：
上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。
也就是说，如果[公式] 在 [公式] 范围内有与 [公式] 重复的字符，我们不需要逐渐增加 [公式] 。 我们可以直接跳过 [公式] 范围内的所有元素，并将 [公式] 变为 [公式] 。
Java（使用 HashMap）
Java（假设字符集为 ASCII 128）
当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换Map。
常用的表如下所示：
执行所有步骤耗去的时间总和为：[公式]
热门标签
