LeetCode 「中等」3.无重复字符的最长子串
题目描述
给定一个字符串s，请你找出其中不含有重复字符的 最长子串的长度。
示例
输入: s = "abcabcbb"
输出: 3
输入: s = "bbbbb"
输出: 1
输入: s = "pwwkew"
输出: 3
解答
滑动窗口
关键思路
- 滑动窗口
- 使用滑动窗口来维护一个不含有重复字符的子串
- 滑动窗口的左右边界分别用两个指针
left和right表示
- 哈希表
- 使用一个哈希表（
Map或对象）来记录每个字符最近一次出现的位置 - 这样可以快速判断当前字符是否已经在窗口中出现过
- 移动窗口
- 遍历字符串，每次将右边界
right向右移动一位 - 如果当前字符已经在窗口中出现过，将左边界
left移动到该字符上次出现位置的右边 - 更新当前字符的最新位置
- 记录当前窗口的长度，更新最长子串的长度
具体步骤
- 初始化
- 初始化左边界
left为 0 - 初始化一个哈希表
charIndex用于记录字符的最新位置 - 初始化最长子串长度
maxLength为 0
- 遍历字符串
- 遍历字符串，每次将右边界
right向右移动一位 - 检查当前字符是否已经在窗口中出现过，如果出现过，更新左边界
left - 更新当前字符的最新位置
- 更新最长子串的长度
- 返回结果
Code
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let left = 0; // 左边界
let maxLength = 0; // 最长子串的长度
const charIndex = new Map(); // 用于记录字符的最新位置
for (let right = 0; right < s.length; ++right) {
const char = s[right]; // 当前字符
// 如果字符已经在窗口中出现过，更新左边界
if (charIndex.has(char)) {
left = Math.max(left, charIndex.get(char) + 1);
}
// 更新当前字符的最新位置
charIndex.set(char, right);
// 更新最长子串的长度
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}