第一种
设置一个滑动窗口，左下标记 l， 右下标记r
r 向右移动，记录每个字符的最后一次出现的位置 m
如果当前字符在 m 中存在,并且重复字符出现的位置在l右侧,让l移动到重复字符的下一个位置,跳过重复的字符
r每次移动时，计算r与l的距离,记录最大值
func lengthOfLongestSubstring(s string) int {
c := []rune(s)
size := len(c)
if size <= 1 {
return size
}
l, r, maxLen, k := 0, 0, 0, 0
ok := false
m := make(map[rune]int, size)
for ; r < size; r++ {
if k, ok = m[c[r]]; ok && k >= l {
l = k + 1
}
if r-l+1 > maxLen {
maxLen = r - l + 1
}
m[c[r]] = r
}
return maxLen
}
第二种
速度与第一种差不多，但内存占用少
func lengthOfLongestSubstring(s string) int {
c := []rune(s)
size := len(c)
if size <= 1 {
return size
}
l, r, maxLen := 0, 0, 0
// 标记字符最后一次出现的位置,不可以使用默认0值，因为下标是从0开始的
m := [128]int{}
for i := 0; i < 128; i++ {
m[i] = -1
}
for ; r < size; r++ {
// 当出现重复字符时，左标记跳到该字符的下一个位置
l = max(l, m[c[r]]+1)
// 记录窗口最大长度
maxLen = max(maxLen, r-l+1)
// 记录字符出现的位置
m[c[r]] = r
}
return maxLen
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}