Golang算法之无重复字符的最长子串

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 911

无重复字符的最长子串，中等难度，leetcode地址：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

1.描述

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

示例 1：

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

1
2
3
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

2.题解

方法一：

这道题拿到手第一感觉可以用for循环暴力解决，我们可以找出其所有子串，挨个判断是否满足条件，对于字符串abcabcbb,它的子串无非就是：

1
2
3
4
a -> ab -> abc -> abca -> abcab -> abcabc -> abcabcb
b -> bc -> bca -> bcab -> bcabc -> bcabcb -> bcabcbb
c -> ca -> cab -> cabc -> cabcb -> cabcbb
...

所以理论上我们只需要2个for循环遍历所有子串，然后判断其是否包含重复字符，更新最大长度，参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func lengthOfLongestSubstring(s string) int {
    if len(s) == 0 {
        return 0 // 处理特殊情况
    }
    max := 1
    for i := 0; i < len(s); i++ {
        for j := i + 1; j <= len(s); j++ {
            subStr := s[i:j]
            if !hasRepeatChar(subStr) && len(subStr) > max {
                max = len(subStr)
                println(subStr)
            }
        }
    }
    return max
}

// 判断是否包含重复字符，可以用map优化
func hasRepeatChar(s string) bool {
    for i := 0; i < len(s); i++ {
        for j := i + 1; j < len(s); j++ {
            if s[i] == s[j] {
                return true
            }
        }
    }
    return false
}

然而，这种方法在leetcode里面没法通过验证，总是报超出时间限制，毕竟这个方法很暴力，也很烂，需要循环很多遍，时间复杂度很高，大约是N3，效率太低了。

方法二:

这道题真正考察的是滑动窗口算法，其算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」

2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串不符合要求（包含重复字符）

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串符合要求，同时，每次增加 left，我们都要更新一轮结果

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头

这种方式效率比较高，只需要遍历一遍，时间复杂度N，参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func lengthOfLongestSubstring(s string) int {
    // 哈希集合，记录每个字符是否出现过，同时也维护了一个窗口内的字符
    m := make(map[byte]int)
    n := len(s)
    // rk右指针，ans是最大长度
    rk, ans := 0, 0
    for i := 0; i < n; i++ {
        if i != 0 {
            // 左指针向右移动一格，移除一个字符
            delete(m, s[i-1])
        }
        for rk < n && m[s[rk]] == 0 {  // 通过map判断是否已存在重复字符
            m[s[rk]] = 1
            rk++  // 不断地移动右指针
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i)
    }
    return ans
}

func max(x, y int) int {
    if x < y {
        return y
    }
    return x
}