滑動(dòng)窗口

1. 什么是滑動(dòng)窗口倡蝙？
   其實(shí)就是一個(gè)隊(duì)列,比如例題中的 abcabcbb缝彬，進(jìn)入這個(gè)隊(duì)列（窗口）為 abc 滿足題目要求缰趋，當(dāng)再進(jìn)入 a，隊(duì)列變成了 abca倘核，這時(shí)候不滿足要求泣侮。所以，我們要移動(dòng)這個(gè)隊(duì)列紧唱！
2. 如何移動(dòng)活尊？
   我們只要把隊(duì)列的左邊的元素移出就行了隶校，直到滿足題目要求！
   一直維持這樣的隊(duì)列蛹锰，找出隊(duì)列出現(xiàn)最長的長度時(shí)候深胳，求出解！

例題

無重復(fù)字符的最長子串

給定一個(gè)字符串铜犬，請你找出其中不含有重復(fù)字符的 最長子串 的長度舞终。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "abc"，所以其長度為 3癣猾。
示例 2:

輸入: "bbbbb"
輸出: 1
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "b"敛劝，所以其長度為 1。
示例 3:

輸入: "pwwkew"
輸出: 3
解釋: 因?yàn)闊o重復(fù)字符的最長子串是 "wke"纷宇，所以其長度為 3夸盟。
     請注意，你的答案必須是 子串 的長度呐粘，"pwke" 是一個(gè)子序列满俗，不是子串转捕。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

求解

求解思路：

• 首先遍歷字符串
• 如果列表中沒有存在當(dāng)前字符作岖，則將當(dāng)前字符添加到列表中
• 如果列表中已存在當(dāng)前字符，則將列表中該字符及之前的字符全部移除五芝，添加當(dāng)前字符痘儡。
• 當(dāng)列表數(shù)據(jù)長度大于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)

代碼優(yōu)化

• 將代碼1中while移除列表元素優(yōu)化為直接操作列表lookup = lookup[index+1:]
• 將代碼1cur_len等局部變量去掉枢步，改為實(shí)時(shí)計(jì)算

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:
                # 有重復(fù)字串, 則將該字符及之前的字符移除
                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

題目發(fā)散

1. 如何知道最長子串的內(nèi)容

• 當(dāng)有重復(fù)字符，移除列表中數(shù)據(jù)時(shí)醉途，起始位置才可能改變
• 但是只有cur_len > max_len矾瑰，才更新max_len，因此這時(shí)的index才是最終的start_index

class Solution(object):

    # 改進(jìn)
    def lengthOfLongestSubstring(self, s):
        if not s:
            return 0

        lookup = []
        max_len = 0
        start_temp_index = 0  
        start_index = 0  # 最終結(jié)果的起始索引
        for i in range(len(s)):
            if s[i] in lookup:
                # 有重復(fù)字串, 則將該字符及之前的字符移除
                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

參考

• 滑動(dòng)窗口