algorithm - 具有 2 个唯一数字的最大连续子数组的长度

Question

我有一个数字数组，我想计算出由 2 个重复的唯一数字组成的连续子数组的最大长度。

例如，[2, 3, 4, 3, 2, 2, 4] 将返回 3，因为 [3, 2, 2] 的长度为 3。

[2, 4, 2, 5, 1, 5, 4, 2] would return 3.
[7, 8, 7, 8, 7] would return 5.

编辑:我考虑过 O(n^2) 解决方案，我从数组中的每个值开始并迭代，直到看到第三个唯一值。

for item in array:
    iterate until third unique element
    if length of this iteration is greater than existing max, update the max length
return maxlength

但是，我认为这不是一个有效的解决方案。

Answer 1

可以做到 O(n)。代码在python3中。 o 和t 分别是一和二。 m 是最大值，c 是当前计数变量。

a = [7, 8, 7, 8, 7]
m = -1
o = a[0]
t = a[1]
# in the beginning one and two are the first 2 numbers 
c = 0
index = 0
for i in a:
    if i == o or i == t:
        # if current element is either one or two current count is increased
        c += 1
    else:
        # if current element is neither one nor two then they are updated accordingly and max is updated
        o = a[index - 1]
        t = a[index]
        m = max(m, c)
        c = 2
    index += 1
m = max(m, c)

print(m)