給定一個字符串琼掠，找出其中不含有重復(fù)字符的最長子串脑溢。
例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 最長子串為 "abc", 其長度為 3.
例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 最長子串為 "b", 其長度為 1.
例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 最長子串為 "wke", 其長度為 3.
注意宴卖，這里要求的是最長子串，”pwke“是一個順序序列衔峰，不是子串佩脊。
條件：
- 字符串的長度在 [0, 5*10^4] 之間。
- 字符串由英文字母垫卤，數(shù)字威彰、符號和空格組成。
解題思路：滑動窗口穴肘，找到最大的窗口抱冷。
第一個想到的方法是用數(shù)組存儲這個最大窗口，實現(xiàn)方式如下：
func lengthOfLongestSubstring(s string) int {
list := make([]int32, 0, len(s))
l, r, longest := 0, 0, 0
for r < len(s) {
vr := int32(s[r])
if isSliceHasValue(list, vr) {
list = slicePop(list)
l++
continue
}
if r-l+1 > longest {
longest = r - l + 1
}
list = append(list, vr)
r++
}
return longest
}
func slicePop(slice []int32) []int32 {
if len(slice) < 1 {
return nil
}
return slice[1:]
}
func isSliceHasValue(slice []int32, v int32) bool {
for _, s := range slice {
if s == v {
return true
}
}
return false
}
但這個“窗口”最大特點是什么梢褐？沒錯，是不存在重復(fù)的字符赵讯，那么盈咳，用 Hash Map 會不會執(zhí)行效率更高？
func lengthOfLongestSubstring(s string) int {
m := make(map[uint8]int)
l, r, longest := 0, 0, 0
for r < len(s) {
vr := s[r]
if times := m[vr]; times > 0 {
vl := s[l]
m[vl]--
l++
continue
}
if r-l+1 > longest {
longest = r - l + 1
}
m[vr]++
r++
}
return longest
}
兩種方式在 LeetCode 里都可以通過边翼，相對而言鱼响，第一種執(zhí)行效率更高，而第二種實現(xiàn)起來更簡單组底，當(dāng)然丈积，你也可以用第三種方式，暴力循環(huán)债鸡。
附
下一題傳送門
