无重复字符的最长子串
🟡 中等题目描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例 1
输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3示例 2
输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1示例 3
输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3提示
0 <= s.length <= 5 * 10^4s由英文字母、数字、符号和空格组成
解法
参考答案 (3 个标签)
滑动窗口 哈希表 O(n)
思路
使用滑动窗口维护一个无重复字符的子串。用哈希表记录每个字符最后出现的位置，当遇到重复字符时，移动窗口左边界。
代码实现
/**
* @param {string} s
* @return {number}
*/
function lengthOfLongestSubstring(s) {
const charIndex = new Map();
let maxLen = 0;
let left = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
if (charIndex.has(char) && charIndex.get(char) >= left) {
left = charIndex.get(char) + 1;
}
charIndex.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}复杂度分析
- 时间复杂度：O(n)，每个字符最多被访问两次
- 空间复杂度：O(min(m, n))，m 为字符集大小
图解
s = "abcabcbb"
步骤 1: [a]bcabcbb left=0, right=0, maxLen=1
步骤 2: [a b]cabcbb left=0, right=1, maxLen=2
步骤 3: [a b c]abcbb left=0, right=2, maxLen=3
步骤 4: a[b c a]bcbb left=1, right=3, maxLen=3 (遇到重复的 a)
步骤 5: a b[c a b]cbb left=2, right=4, maxLen=3 (遇到重复的 b)
...