时间戳

首页 > 解决方案 > 计算子数组的数量，使得子数组中的每个元素至少出现两次

python - 计算子数组的数量，使得子数组中的每个元素至少出现两次

问题描述

我遇到了一个问题，似乎无法提出有效的解决方案。问题如下：

给定一个数组 A，计算连续连续子数组的数量，使得子数组中的每个元素至少出现两次。

例如，对于：

A = [0,0,0]

答案应该是 3 因为我们有

A[0..1] = [0,0]
A[1..2] = [0,0]
A[0..3] = [0,0,0]

另一个例子：

A=[1,2,1,2,3]

答案应该是 1，因为我们有：

A[0..3] = [1,2,1,2]

我似乎无法为这个算法想出一个有效的解决方案。我有一个算法可以检查每个可能的子数组（O（n ^ 2）），但我需要更好的东西。这是我天真的解决方案：

def duplicatesOnSegment(arr):
    total = 0
    for i in range(0,len(arr)):
        unique = 0
        test = {}
        for j in range(i,len(arr)):
            k = arr[j]
            if k not in test:
                test[k] = 1
            else:
                test[k] +=  1

            if test[k] == 1:
                unique += 1
            elif test[k] == 2:
                unique -= 1
            if unique == 0:
                total += 1
    return total

标签： pythonlistcomplexity-theory

解决方案

if k not in test当您在嵌套循环中使用时，您的程序在最坏的情况下大于 O(n^2) 。这in在最坏的情况下是 O(n)，导致整体最坏的情况为 O(n^3)。我有这个，最坏的 O(n^2) 解决方案，它collections.defaultdict用作散列以使其更快。

from collections import defaultdict

def func(A):
    result = 0
    for i in range(0,len(A)):
        counter = 0
        hash = defaultdict (int)
        for j in range (i, len(A)):
            hash[A[j]] += 1
            if hash[A[j]] == 2:
                counter += 1
            if counter != 0 and counter == len(hash):
                result += 1
    return result

推荐阅读