滑动窗口
- 什么是滑动窗口？
其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
- 如何移动？
我们只要把队列的左边的元素移出就行了，直到满足题目要求！
一直维持这样的队列，找出队列出现最长的长度时候，求出解！
例题
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
求解
求解思路：
- 首先遍历字符串
- 如果列表中没有存在当前字符，则将当前字符添加到列表中
- 如果列表中已存在当前字符，则将列表中该字符及之前的字符全部移除，添加当前字符。
- 当列表数据长度大于
max_len，则更新
代码1
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
left = 0
lookup = set()
n = len(s)
max_len = 0
cur_len = 0
for i in range(n):
cur_len += 1
while s[i] in lookup:
lookup.remove(s[left])
left += 1
cur_len -= 1
if cur_len > max_len: max_len = cur_len
lookup.add(s[i])
return max_len
if __name__ == '__main__':
obj = Solution()
str_input = "abcabcbb"
result = obj.lengthOfLongestSubstring(str_input)
print('result:', result)
代码优化
- 将代码1中
while移除列表元素优化为直接操作列表lookup = lookup[index+1:]
- 将代码1
cur_len等局部变量去掉，改为实时计算
class Solution(object):
def lengthOfLongestSubstring(self, s):
if not s:
return 0
lookup = []
max_len = 0
for i in range(len(s)):
if s[i] in lookup:
# 有重复字串, 则将该字符及之前的字符移除
index = lookup.index(s[i])
lookup = lookup[index+1:]
lookup.append(s[i])
cur_len = len(lookup)
if cur_len > max_len:
# 将新的字符添加后，更新最长的长度
max_len = cur_len
return max_len
题目发散
- 如何知道最长子串的内容
- 当有重复字符，移除列表中数据时，起始位置才可能改变
- 但是只有
cur_len > max_len，才更新max_len，因此这时的index才是最终的start_index
class Solution(object):
# 改进
def lengthOfLongestSubstring(self, s):
if not s:
return 0
lookup = []
max_len = 0
start_temp_index = 0
start_index = 0 # 最终结果的起始索引
for i in range(len(s)):
if s[i] in lookup:
# 有重复字串, 则将该字符及之前的字符移除
index = lookup.index(s[i])
lookup = lookup[index + 1:]
start_temp_index = index + 1
lookup.append(s[i])
cur_len = len(lookup)
if cur_len > max_len:
# 将新的字符添加后，更新最长的长度
max_len = cur_len
start_index = start_temp_index # 更新最终的起始索引
print('result str:', s[start_index:start_index+max_len])
return max_len
参考
