2021 年 06 月 23 日 链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
题目
描述
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。
提示
0 <= s.length <= 5 * 10
-
解答
设置 minIndex 作为左指针,指向不重复的字符串的首字符
- 设置 maxLength 用于记录不重复字符串的最大长度,因为当前不重复字符串可能不是最大字符串,所以需要用 maxLength 记录
- 遍历字符串,i 作为遍历索引也作为右指针
- 设置 map 存放遍历过程中的每个字符,以当前字符作为 key,当前索引作为 i。如果遇到重复字符则更新
- 用此种规则存放字符,如果出现重复字符则会更新,比如字符串 “abcba”,当
i === 3
时 map 中的 “key = b” 的值就会从 1 更新到 3 - 同时 map 中还会存放着垃圾数据,比如字符串 “abcba”,当
i === 3
时 map 中的 “key = b” 的值更新为了 3,此时说明窗口已经滑动到了 “c” 字符的位置,所以此时 map 中的 “key = a” 则为无效字符;当i === 4
时当前字符为 “a” 此时查询 map 能查到对应的字符 “key = a” 但是因为它已经是无效字符,所以此时的“a”不是重复字符,因此需要 minIndex 来控制窗口左边位置,当从 map 中查询到的字符时,此字符对应的索引 value 只有在 minIndex 要求的范围内,才算重复字符
- 用此种规则存放字符,如果出现重复字符则会更新,比如字符串 “abcba”,当
- 设置 curIndex 存放当前项 map 中取出的值
- 遍历过程中,如果 curIndex >= minIndex 代表当前字符已经出现过,并且在窗口内,则证明此时发生了重复,所以可以将左指针移向与当前位置重复的位置的下一个位置,比如字符串 “abcba”,当
i===3
时,与i===1
的位置重复了,此时将左指针移动到i===2
的位置 - 当前不重复字符串的长度等于当前索引 i + 1 - minIndex,如果当前长度比历史的最大长度长,则更新历史的最大长度
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
// 字符字典
const dic = new Map()
// 左指针
let minIndex = 0
// 历史最大长度
let maxLength = 0
// 当前字符在 map 中存放的索引
// 即当前字符上次出现的索引
let curIndex
for(let i = 0; i < s.length; i ++){
curIndex = dic.get(s[i])
// 如果上次出现的索引比左指针大,则证明字符重复发生在窗口内,重复有效
if(curIndex >= minIndex){
// 将左指针移动到上此出现的索引的下一位,缩小当前窗口
minIndex = curIndex + 1
}
// 将当前字符存放到 map 中,并记录最新索引
dic.set(s[i], i)
// 将当前统计的不重复字符串的长度与历史不重复字符串的长度对比,存储最大值
maxLength = Math.max(i + 1 - minIndex, maxLength)
}
return maxLength
};