如果这个值出现过,那么把 left ++,缩进左边界,并且记得把 str[left] 位置的值在 freqMap 中减掉。
循环条件是 left < str.length,允许左边界一直滑动到字符串的右界。
/**
* @param {string} s
* @return {number}
*/
let lengthOfLongestSubstring = function (str) {
let n = str.length
// 滑动窗口为s[left...right]
let left = 0
let right = -1
let freqMap = {} // 记录当前子串中下标对应的出现频率
let max = 0 // 找到的满足条件子串的最长长度
while (left < n) {
let nextLetter = str[right + 1]
if (!freqMap[nextLetter] && nextLetter !== undefined) {
freqMap[nextLetter] = 1
right++
} else {
freqMap[str[left]] = 0
left++
}
max = Math.max(max, right - left + 1)
}
return max
}
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
示例 2:
示例 3:
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这题是比较典型的滑动窗口问题,定义一个左边界
left
和一个右边界right
,形成一个窗口,并且在这个窗口中保证不出现重复的字符串。这需要用到一个新的变量
freqMap
,用来记录窗口中的字母出现的频率数。在此基础上,先尝试取窗口的右边界再右边一个位置的值,也就是str[right + 1]
,然后拿这个值去freqMap
中查找:right ++
,扩大窗口右边界。left ++
,缩进左边界,并且记得把str[left]
位置的值在freqMap
中减掉。循环条件是
left < str.length
,允许左边界一直滑动到字符串的右界。