Как перебрать все отдельные тройки массива так, чтобы они имели формат (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).
Это был мой первый перебор (для начала, O(n^3)):

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

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())

Помощь была бы очень оценена.

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