解题思路
初始:abcdfde
- 当没有重复值时,滑动窗口一直累加:
第一个滑动窗口:abcdf,窗口长度5 - 当有重复值“d”时
因为abcdf已经确认过为无重复序列了,所以这一段是不需要重新比较的,只需要更新重复字符中前一个d的下一个字符串f为新窗口的初始值
第二个滑动窗口:fde,窗口长度3 - 取最大窗口长度:5
实现过程:
- 创建一个哈希表,用来保存当前滑动窗口里的字符串,滑动窗口里的集合代表着不存在重复的子序列,指针start代表滑动窗口初始下标,初始为0
- 遍历str,当前遍历下标为i,如果遍历的当前字符不在哈希表中,则将当前的字符保存到哈希表,且滑动窗口长度=i - start + 1;如果长度比历史长度大,则更新此值为最大值;比如“abcbde”,当滑动到"c"时,winLen = 3
- 如果当前字符存在哈希表中,查看其在哈希表中记录的位置,start指针开始的移动,直至当前字符存在的位置的下一位,在这过程中哈希表将这些值都删掉,当移动到“b”时,发现b在哈希表有值,且对应下标是1,start移动到它的下一位2的位置,然后删除"ab"在哈希表的值,哈希表更新为"cb"
- 然后继续遍历str,重复1,2,3过程,直至结束,就能得出最大不重复子序列了。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let len = s.length;
// 边界值,如果小于1个值,那么最长子串为它的长度
if(len <= 1) {
return len;
}
// 创建一个哈希表,保存当前滑动窗口的集合
let map = new Map()
// 记录最大长度
let maxLen = 0;
// 滑动窗口的初始位置
let start = 0;
// 当前滑动窗口的长度
let winLen = 0;
// 遍历字符串
for(let i = 0; i < len; i++) {
// 如果当前字符不存在哈希表,则将字符和其下标保存到哈希表中
if(!map.has(s[i])) {
// 更新滑动窗口长度
winLen = i - start + 1
// 如果滑动窗口大于最大长度,则更新最大长度
if(winLen > maxLen) {
maxLen = winLen
}
// 如果当前字符存在哈希表中,代表着有重复值,要更新哈希表
}else {
// start要移动到的位置,为之前这个字符的下标+1
let newStart = map.get(s[i]) + 1
// 滑动start到新位置,并将其中的字符在哈希表中删除
while(start != newStart) {
map.delete(s[start])
start++;
}
}
// 将当前遍历的值和其下标,更新到哈希表中
map.set(s[i], i)
}
return maxLen
};
let str1 = "abcdfde"
let str2 = "abcabcbb"
let res = lengthOfLongestSubstring(str1)
console.log(res) // 5
网友评论