NC41 最长无重复子数组

题目描述

给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。

示例1
输入：
[2,3,4,5]
复制
返回值：
4
说明：
[2,3,4,5]是最长子数组

示例2
输入：
[2,2,3,4,3]
复制
返回值：
3
说明：
[2,3,4]是最长子数组

示例3
输入：
[9]
复制
返回值：
1

示例4
输入：
[1,2,3,1,2,3,2,2]
复制
返回值：
3
说明：
最长子数组为[1,2,3]

示例5
输入：
[2,2,3,4,8,99,3]
复制
返回值：
5
说明：
最长子数组为[2,3,4,8,99]

解题思路

在检查每一个子串的时候，可以用哈希表检测有没有遇到重复的数字。
一种很容易想到的方法为：

class Solution:
    def maxLength(self, arr):
        result = 0
        length = len(arr)
        for i in range(length):
            visited = {}
            temp = 0
            for j in range(i, length):
                if arr[j] not in visited:
                    visited[arr[j]] = j
                    temp += 1
                else:
                    break
            result = max(result, temp)
        return result

但是这种方法的时间复杂度非常高。
以1 3 2 5 2 4 2 7为例，当我们从1开始遍历的时候，遍历到了j = 4的时候会因为碰到两个2而停下来，下一次遍历的arr[i]为1。但实际上这是没有必要的，因为从3开始遍历，还是会因为碰到同样的两个2会停下来。
像这种老是遇到两个2的情况，在察觉到是因为2而导致重复的情况时，可以记住第一次出现2的位置，下次可以直接从5开始遍历子字符串，这样可以跳过大量的子串的遍历。

解题代码

class Solution:
    def maxLength(self, arr):
        result = 0
        length = len(arr)
        i = 0
        while i < length:
            visited = {}
            temp = 0
            for j in range(i, length):
                if arr[j] not in visited:
                    visited[arr[j]] = j
                    temp += 1
                else:
                    i = visited[arr[j]]
                    visited[arr[j]] = i
                    break
            i += 1
            result = max(result, temp)
        return result

执行结果

92ms 12440KB