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

最长无重复子数组

http://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4

#
# 使用双指针方法时间复杂度为n
#

# @param arr int整型一维数组 the array
# @return int整型
#
class Solution:
    def maxLength(self , arr: List[int]) -> int:
        # write code here
        if len(arr)<=1:
            return len(arr)
        # 初始化左右指针
        l, r = 0, 1
        res = 1
        # 右指针遍历完位置,时间复杂度为n
        for r in range(len(arr)):
            # 若右指针元素与arr[l:r]中有重复,左指针更新为重复元素的指针+1,此不重复字列表长度为r-l
            if arr[r] in arr[l:r]:
                res = max(res, r-l)
                l = arr[l:r].index(arr[r])+l+1
            # 若无重复,此不重复列表长度为r-l+1
            else:
                res = max(res, r-l+1)
        return res
全部评论

相关推荐

06-05 19:46
已编辑
武汉大学 后端
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务