0003.无重复字符的最长子串
难度:🟡 中等
标签:哈希表
、字符串
、滑动窗口
题目描述
给定一个字符串 s
,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
解题思路
核心思想
本题的目标是找到一个最长的、不包含重复字符的连续子串。解决这个问题的核心在于如何高效地维护和更新一个“当前没有重复字符”的子串,并记录其最大长度。
思路选择
滑动窗口法 是解决此问题的标准最优思路。
我们使用两个指针,
left
和right
,来定义一个“窗口”,这个窗口内的子串是我们当前正在考察的无重复字符的子串。right
指针负责向右扩展窗口,left
指针则在窗口内出现重复字符时向右收缩。为了能快速判断一个字符是否在当前窗口内出现过,并找到它上次出现的位置,我们使用一个 哈希表(Map) 来存储窗口内每个字符及其最新的索引。
关键步骤
初始化:初始化左指针
left = 0
,最大长度maxLength = 0
。创建一个哈希表map
用于存储字符和它们的索引。循环遍历:用右指针
right
从 0 开始遍历整个字符串s
。检查重复与收缩窗口: a. 对于当前字符
s[right]
,检查它是否已存在于map
中。 b. 如果存在,并且它上一次出现的位置map.get(s[right])
大于等于当前窗口的左边界left
,说明该字符在当前窗口内重复了。我们需要收缩窗口,将左指针left
移动到重复字符的下一个位置,即left = map.get(s[right]) + 1
。扩展窗口与更新: a. 无论是否重复,都更新
map
中当前字符s[right]
的索引为最新的位置right
。 b. 计算当前窗口的长度right - left + 1
,并用它来更新maxLength
。返回结果:遍历结束后,
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
的长度。我们只需要对字符串进行一次完整的遍历,left
和right
指针都只向前移动。空间复杂度:O(min(m, n)) 其中 n 是字符串长度,m 是字符集的大小(例如 ASCII 码为 128)。空间消耗取决于哈希表中存储的不同字符的数量,最多为
min(m, n)
。
相关题目
总结
本题是滑动窗口算法的经典入门题。其核心在于理解如何通过双指针和哈希表来维护一个动态的、符合条件的“窗口”,并在遍历过程中不断更新最优解。这个模型在解决各类子串/子数组问题时非常强大。