题解 | #最长无重复子数组#

滑动窗口

#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self, arr):
        # write code here
        # 滑动窗口
        windows = 1
        cur = dict()
        chongfu = set()
        if len(arr) == 0:
            return 0
        begin = 0
        cur[arr[0]] = 1
        while (begin + windows < len(arr)):
            while begin + windows < len(arr) and (arr[begin + windows] not in cur) :
                cur[arr[begin + windows]] = 1
                windows += 1

            if begin + windows >= len(arr):
                break
            if cur[arr[begin]] == 1:
                cur.pop(arr[begin])
            else:
                cur[arr[begin]] = cur[arr[begin]] - 1
                if cur[arr[begin]] == 1:
                    chongfu.remove(arr[begin])
            if arr[begin + windows] not in cur:
                cur[arr[begin + windows]] = 1
            else:
                cur[arr[begin + windows]] += 1
                chongfu.add(arr[begin + windows])
            begin += 1
            while (begin + windows < len(arr) and len(chongfu) > 0):
                if cur[arr[begin]] == 1:
                    cur.pop(arr[begin])
                else:
                    cur[arr[begin]] = cur[arr[begin]] - 1
                    if cur[arr[begin]] == 1:
                        chongfu.remove(arr[begin])
                if arr[begin + windows] not in cur:
                    cur[arr[begin + windows]] = 1
                else:
                    cur[arr[begin + windows]] += 1
                    chongfu.add(arr[begin + windows])
                begin += 1
        return windows