无重复字符的最长子串
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
|
解法
1
2
3
4
5
6
7
8
9
|
这是一个经典的字符串处理问题，题目要求找出一个字符串中不含有重复字符的最长子串的长度。
解决这个问题的一个常见方法是使用滑动窗口。滑动窗口是一个动态的子字符串，我们可以通过移动窗口的左边界和右边界来改变窗口的大小。在这个问题中，我们可以使用两个指针（left 和 right）来表示窗口的左边界和右边界。
初始时，left 和 right 都指向字符串的开始位置。然后我们逐渐向右移动 right 指针，如果 right 指向的字符在窗口中没有出现过，那么就将这个字符加入窗口；如果 right 指向的字符在窗口中已经出现过，那么就向右移动 left 指针，直到这个字符不再在窗口中出现，然后再将这个字符加入窗口。
在这个过程中，每次移动 right 指针后，窗口中的字符就是一个没有重复字符的子串，我们可以记录下这个子串的长度。最后，所有这些长度中的最大值就是我们要找的答案。
这个方法的时间复杂度是 O(n)，其中 n 是字符串的长度。因为每个字符最多被 left 和 right 指针各访问一次，所以总的操作次数是 2n，因此时间复杂度是 O(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
28
29
30
31
32
33
34
35
36
|
package main
import "fmt"
func lengthOfLongestSubstring(s string) int {
window := make(map[rune]int)
left, right, res := 0, 0, 0
for right < len(s) {
c := rune(s[right])
right++
// 更新窗口数据
window[c]++
// 当窗口内有重复字符时，移动 left 缩小窗口
for window[c] > 1 {
d := rune(s[left])
left++
window[d]--
}
// 更新结果
if right-left > res {
res = right - left
}
}
return res
}
func main() {
fmt.Println(lengthOfLongestSubstring("abcabcbb")) // 输出: 3
fmt.Println(lengthOfLongestSubstring("bbbbb")) // 输出: 1
fmt.Println(lengthOfLongestSubstring("pwwkew")) // 输出: 3
}
|
另一个更简洁的解法
首先，如果输入的字符串 s 的长度小于 2，那么最长的无重复字符的子串就是 s 本身，所以直接返回 s 的长度。
然后，定义了四个变量：left 和 right 分别表示滑动窗口的左右边界，maxLength 用来记录最长的无重复字符的子串的长度，exists 是一个字典，用来记录每个字符最后出现的位置。
接下来，开始遍历字符串 s。在每次循环中，首先检查 right 指向的字符是否在 exists 中，如果在，说明这个字符在 left 和 right 之间已经出现过，所以需要移动 left 到这个字符上一次出现的位置的下一个位置，这样 left 和 right 之间的子串就不包含重复的字符。这里使用 maxIn 函数是为了防止 left 向左移动。(比如这总情况abcbacc)
然后，将 right 指向的字符和其位置添加到 exists 中，这样在下次遇到这个字符时就可以知道它上一次出现的位置。
接着，如果right - left + 1 大于 maxLength，就更新 maxLength。这是因为 right - left + 1 就是 left 和 right 之间的子串的长度，如果这个长度大于 maxLength，说明找到了一个更长的无重复字符的子串。
最后，将 right 向右移动一位，继续下一次循环。
当所有的字符都被遍历过后，返回 maxLength，这就是无重复字符的最长子串的长度。
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
|
func longestsubstring(s string) int {
if len(s) < 2 {
return len(s)
}
var (
left = 0
right = 0
maxLength = 0
exists = map[byte]int{}
)
for right < len(s) {
if idx, ok := exists[s[right]]; ok {
left = maxIn(left, idx+1)
}
exists[s[right]] = right
if right-left+1 > maxLength {
maxLength = right - left + 1
}
right++
}
return maxLength
}
|