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
	}
}

           

執行結果如下：