Как пройти через все отдельные триплеты массива, так что они имеют формат (A, B, B)? Длина массива <= 10^6 ⇐ Python

[Anonymous]

Как указано выше, мне нужно эффективно подсчитать количество отдельных триплетов формы (A, B, B). Кроме того, тройка действительна только тогда, когда и только тогда, когда он может быть сформирован, удалив некоторые целые числа из массива, оставив только этот триплет в этом конкретном порядке. Я полагаю, что это говорит о том, что триплеты должны быть в хронологическом порядке, но не должны состоять из последовательных элементов. Решение должно быть действительно эффективным, так как N (длина массива) может подняться до 10^6 (или миллион). Например, если бы массив был [5, 6, 7, 3, 3, 3], то ответ был бы 3, поскольку триплеты будут: (5, 3, 3), (6, 3, 3), и и (7, 3, 3). < /P>
Это была моя первая грубая сила (просто для начала, O (n^3)): < /p>

Код: Выделить всё

n = int(input())
arr = list(map(int, input().split()))

ans = set()
for i in range(n):
for j in range(i + 1, n):
if arr[i] != arr[j]:
for k in range(j + 1, n):
if arr[j] == arr[k]:
ans.add((arr[i], arr[j], arr[k]))

print(len(ans))

Затем я безуспешно пытался оптимизировать это до O(n^2), что по-прежнему слишком медленно, но я даже не могу сделать это правильно:

Код: Выделить всё

def solve():
n = int(input())
arr = list(map(int, input().split()))

freq = Counter(arr)
ans = set()
for a in freq:
if freq[a] < 1:
continue
for b in freq:
if b != a and freq[b] >= 2:
ans.add((a, b, b))

return len(ans)

print(solve())

Я не могу исправить логику для O(n^2) и оптимизировать ее, чтобы полностью решить проблему при заданных ограничениях. Помощь будет очень признательна.

Подробнее здесь: https://stackoverflow.com/questions/793 ... are-of-the