求一个字符串中,最长无重复字符子串长度。
方法一:滑动窗口。自然智慧。
不重复的时候,右指针右移;重复的时候,左指针右移。
方法二:求出最右不重复位置。
map:key是值,value是数组序号,初始值value都是-1。
时间复杂度:O(N)。空间复杂度:O(不同字符个数)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
s := "moonfdd"
ret1 := lengthOfLongestSubstring1(s)
fmt.Println(ret1)
ret2 := lengthOfLongestSubstring2(s)
fmt.Println(ret2)
}
//方法一:滑动窗口。自然智慧。
func lengthOfLongestSubstring1(s string) int {
// 哈希集合,记录每个字符是否出现过
m := map[byte]int{}
n := len(s)
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
rk, ans := -1, 0
for i := 0; i < n; i++ {
if i != 0 {
// 左指针向右移动一格,移除一个字符
delete(m, s[i-1])
}
for rk+1 < n && m[s[rk+1]] == 0 {
// 不断地移动右指针
m[s[rk+1]]++
rk++
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = getMax(ans, rk-i+1)
}
return ans
}
//方法二:求出最右不重复位置。
func lengthOfLongestSubstring2(s string) int {
if len(s) == 0 {
return 0
}
indexList := make([]int, 256)
for i := 0; i < 256; i++ {
indexList[i] = -1
}
N := len(s)
ans := 0
p := -1
for i := 0; i < N; i++ {
p = getMax(p, indexList[s[i]])
ans = getMax(ans, i-p)
indexList[s[i]] = i
}
return ans
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
func getMin(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下: