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

无重复字符的最长子串,中等难度,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
}