滑动窗口
解题思路
定义变量 maxLen 表示最大长度，定义一个 map 用来存储出现过的字符和该字符的索引；
使用双指针 left、right 截取不含重复字符的子串；
- left 和 right 初始值都是 0 ，right 不断右移，不断将 right 位置的字符放到 map 中，如果不存在重复字母 right 不断右移，计算子串长度
right - left + 1，保留较大值到 maxLen；- 如果存在重复字母，left 直接移动到重复字母的索引位置+1 （只取索引大于 left 的重复字母的索引，因为重复字母的索引可以出现在 left 左侧，即已经不在窗口范围内的字母）；
复杂度：
-
时间复杂度：
O(n)，因为要遍历整个字符串； -
空间复杂度：
O(n)，最坏情况下字符串可能不重复；
代码实现
var lengthOfLongestSubstring = function (s) {
let map = new Map();
let left = 0, right = 0, maxLen = 0;
while (right < s.length) {
let letter = s[right];
if (map.has(letter)) {
let inx = map.get(letter) + 1;
left = left > inx ? left : inx;
}
map.set(letter, right);
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
118.杨辉三角
上一篇
评论
