3. 最长不重复子串

给定一个字符串，找出其中不含有重复字符的最长子串。

例 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 里都可以通过，相对而言，第一种执行效率更高，而第二种实现起来更简单，当然，你也可以用第三种方式，暴力循环。

附

下一题传送门