大约 1 分钟
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// 哈希集合,记录每个字符是否出现过
const set = new Set();
const n = s.length;
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
let right = -1;
let maxLen = 0;
for (let left = 0; left < n; left++) {
// 左指针向右移动一格,移除一个字符
if (left !== 0) {
set.delete(s.charAt(left - 1));
}
// 不断地向右移动右指针,直到遇到重复字符或者到达字符串末尾
while (right + 1 < n && !set.has(s.charAt(right + 1))) {
set.add(s.charAt(right + 1));
right++;
}
// 第 left 到 right 个字符是一个极长的无重复字符子串
// 长度为 right - left + 1
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};
更简洁的写法(优化版)
下面这种写法逻辑更直观:遇到重复字符时,直接收缩左边界。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let maxLen = 0;
let left = 0;
const charSet = new Set();
for (let right = 0; right < s.length; right++) {
// 当前字符
const currentChar = s[right];
// 如果 Set 中存在该字符,说明重复了
// 移动左指针,并删除左指针经过的字符,直到 Set 中不包含当前字符
while (charSet.has(currentChar)) {
charSet.delete(s[left]);
left++;
}
// 将当前字符加入 Set
charSet.add(currentChar);
// 更新最大长度 (当前窗口大小为 right - left + 1)
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};