两遍 for 循环,结果超时 (go 代码)
func lengthOfLongestSubstring(s string) int {
// 存放当前找到的最长子字符串
length := 0
for i := 0; i < len(s); i++ {
// 查找当前循环内最长的子字符串,使用 map 来判断是否重复
maps := make(map[string]int)
// 当前字符串放入 map 内
index := 0
maps[string([]rune(s)[i])] = index
index++
// 遍历后续的字符串,判断是否重复,不重复则放入 map,重复直接 break
for n := i + 1; n < len(s); n++ {
k := string([]rune(s)[n])
if _, ok := maps[k]; ok {
break
} else {
maps[k] = index
index++
}
}
// 对比之前的结果
if index > length {
length = index
}
}
return length
}
修正为滑动窗口,取上标 s 下标 e,当 e +1 存在于 s 与 e 之间,则把 s 滑动到 e+1对应的 index 的下一个位置,不存在于 s 与 e 之间,则把 e 滑动到 e+1的位置,并且判断记录 max,直到结束(js 代码)
const fun = s => {
if (s.length <= 0) return 0;
// 记录最长值
let max = 1;
// 起始下标
let start = 0;
// 结束下标
let end = 1;
// 循环,结束坐标大于等于字符串长度就结束
while (end < s.length) {
// 判断结束下标的后一位是不是和 起始下标-结束下标之间的字符串重复
const i = s.slice(start, end).indexOf(s[end]);
// 如果重复了,起始下标移动到重复元素的下一个元素
if (i !== -1) {
start += i + 1;
// 如果起始坐标和结束是同一个,结束朝后移动一位
if (start === end) {
end += 1;
}
} else {
// 如果没有重复,结束下标朝后移动一位,判断一下当前字符串是不是大于当前最大值,大于则记录下来
end += 1;
if (end - start > max) {
max = end - start;
}
}
}
};
fun("aaaaaabsabwqdcde")