无重复的最长的子字符串
力扣第3题:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
1 暴力解决
暴力方法就是将所有的肯恩列举出来,在会超过时间限制,这里就不列举了
2 滑动窗口
这道题是我第一道碰到的滑动窗口的题目,当时想了很久都想不出来,后来去看一一下别人的题解恍然大悟,滑动窗口确实是解决字符串问题的一非常好的方法
滑动窗口的顾名思义就是可以滑动的数据结构,遍历整个字符串,当滑动窗口里没有该字符时,就将该字符加进滑动窗口
当遇到有重复字符时,要将滑动窗口该字符前面的的字符(包括该字符)全部去除,然后在将该字符加进滑动窗口
代码如下:
1 | class Solution: |
2.1 复杂度分析
时间复杂度:遍历了一次数组,时间复杂度为$$0(N)$$, 但是每次滑动窗口的都有重复字符,如字符串为’aaaaaaaaaaaaaaaaaaa’,会浪费没必要的时间,但是均摊时间复杂度依然为$$O(N)$$
空间复杂度:用了集合,所以空间复杂度为$$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
24class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s :return 0
silde_win = set()
left = 0
max_len = 0
cur_len = 0
for i in range(len(s)):
# 如果字符串有相邻的子串,直接忽视
if i > 0 and s[i-1] == s[i]:
silde_win = set()
silde_win.add(s[i])
left = i
cur_len = 1
continue
cur_len += 1
# 设置滑动窗口的值
while s[i] in silde_win:
silde_win.remove(s[left])
left += 1
cur_len -= 1
silde_win.add(s[i])
max_len = max(max_len, cur_len)
return max_len
可以发现成绩有了提升,但不是很明显
- 然后在看看我么你写的代码,silde_win这个数据结构其实是有很多操作的,话费了很多时间,换个思路想一想,我们能又能用更好地数据结构来代替这个集合呢,其实这个滑动窗口只是一个辅助的数据结构,只是用来暂时存储字符串的字串的,那为什么不直接用分片呢
1 | class Solution: |
