知食记
搜索文档…
3. 无重复字符最长字串

题目

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew" changdu
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。 请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

思路1 暴力解

逐个检查所有的子字符串,看它是否不含有重复的字符。

思路2 滑动窗口

在暴力法中,我们会反复检查一个子字符串是否含有有重复的字符,但这是没有必要的。
滑动窗口是数组/字符串问题中常用的抽象概念。 窗口通常是在数组/字符串中由开始和结束索引定义的一系列元素的集合,即 [i, j)[i,j)(左闭,右开)。而滑动窗口是可以将两个边界向某一方向“滑动”的窗口。例如,我们将 [i, j)[i,j) 向右滑动 11 个元素,则它将变为 [i+1, j+1)[i+1,j+1)(左闭,右开)
滑动窗口的解法是:
  1. 1.
    设置内外两层循环i , j ; i为外层循环,j为内层循环, 使用数组win来存储[i, j)的数字
  2. 2.
    如果s[j]值存在于[i,j), 那么下次设置 i = i + 1
  3. 3.
    如果s[j]值不存在与[i,j), 那么设置 j = j + 1
  4. 4.
    最后统计最大的win长度

思路3 优化滑动窗口

在思路2的基础上,让s[j]值存在与[i,j)中时,把i直接跳到[i,j)中s[j]值索引的下一位

JavaScript实现

/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const infoMap = new Map();
let i = j = maxSub = 0;
for(let i = j = 0; j < s.length; j++){
if(infoMap.has(s.charAt(j))){
i = Math.max(infoMap.get(s.charAt(j)), i);
}
maxSub = Math.max(maxSub, j-i+1);
infoMap.set(s.charAt(j), j+1);
}
return maxSub;
};
复制链接
大纲
题目
思路1 暴力解
思路2 滑动窗口
思路3 优化滑动窗口
JavaScript实现