题解 | 最长无重复子数组-leetcode3

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:

    """
    mp =dict() 记录窗口内的非重复字符
    aba  a:2  b=1
    right=1 
    left =0 
    right=2 时候  mp={a:2,b:1}
    移除最左侧a的次数 此时 mp={a:1:b:1} mp[right]=a次数==1
    比较次数
    官方题解：
    1:  构建哈希表统计每个元素出现的次数
    2:  窗口左右边界都是从0 开始left ,right =0 
     外侧遍历right 指针，统计arr[right] 次数
    3. 出现mp[right]>1 ，mparr[left]]-=1
       left+=1
    4 .res=max(res.right-left+1)
    """
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        if not arr:
            return 0
        if len(arr)==1:
            return 1 
        n=len(arr)
        res =0
        left=0
        mp=dict()
        for right in range(n):
            if arr[right] not in mp:
                mp[arr[right]]=1
            else:
                mp[arr[right]]+=1
            while mp[arr[right]]>1:
                mp[arr[left]]-=1
                left+=1
            res =max(res,right-left+1)

        return res 


    """
    set + 移除最左侧的元素   leetcode 官方题解
    """
    def maxLength1(self , arr: List[int]) -> int:
        # write code here
        if not arr:
            return 0
        if len(arr)==1:
            return 1 
        n=len(arr)
        res =0
        temp=set()
        rk=-1
        for i in range (n):
            # 移除左侧起始位置
            if i>0:  # 这一步不叫
                temp.remove(arr[i-1])
            
            while rk+1<n and arr[rk+1] not in temp:
                    temp.add(arr[rk+1])
                    rk+=1
            res=max(res ,rk-i+1)
        return  res