滑动窗口1:无重复字符的最长子串

滑动窗口

1. 什么是滑动窗口？
   其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！
2. 如何移动？
   我们只要把队列的左边的元素移出就行了，直到满足题目要求！
   一直维持这样的队列，找出队列出现最长的长度时候，求出解！

例题

无重复字符的最长子串

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

示例 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:]
• 将代码1cur_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

题目发散

1. 如何知道最长子串的内容

• 当有重复字符，移除列表中数据时，起始位置才可能改变
• 但是只有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

参考

• 滑动窗口