给定一个字符串，找出其中不含有重复字符的最长子串。
例 1:
输入: s = "abcabcbb"
输出: 3
解释: 最长子串为 "abc", 其长度为 3.
例 2:
输入: s = "bbbbb"
输出: 1
解释: 最长子串为 "b", 其长度为 1.
例 3:
输入: s = "pwwkew"
输出: 3
解释: 最长子串为 "wke", 其长度为 3.
注意，这里要求的是最长子串，”pwke“是一个顺序序列，不是子串。
条件：
- 字符串的长度在 [0, 5*10^4] 之间。
- 字符串由英文字母，数字、符号和空格组成。
解题思路：滑动窗口，找到最大的窗口。
第一个想到的方法是用数组存储这个最大窗口，实现方式如下：
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
}
但这个“窗口”最大特点是什么？没错，是不存在重复的字符，那么，用 Hash Map 会不会执行效率更高？
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 里都可以通过，相对而言，第一种执行效率更高，而第二种实现起来更简单，当然，你也可以用第三种方式，暴力循环。
附
下一题传送门
