2021-06-24：如何计算字符串中最长不重复子串的长度？

本文共计534个文字，预计阅读时间需要3分钟。

2021-06-24：找出字符串中，最长的无重复字符子串长度。福大大+答案：方法一：滑动窗口。自然智能。不重复时，右指针右移；重复时，左指针右移。方法二：求出最长无重复子串。

2021-06-24：求一个字符串中，最长无重复字符子串长度。

福大大 答案2021-06-24：

方法一：滑动窗口。自然智慧。
不重复的时候，右指针右移；重复的时候，左指针右移。

方法二：求出最右不重复位置。
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 } }

执行结果如下：