Chương trình đếm cặp chỉ số có giá trị bằng nhau trong mảng Python

Cho danh sách nums. Đếm số cặp i < j sao cho nums[i] == nums[j].

Ví dụ: nums = [5, 4, 5, 4, 4] → kết quả 4. Các cặp: (0,2), (1,3), (1,4), (3,4).

Thuật toán giải quyết (O(n))

1. Dùng Counter đếm tần suất mỗi giá trị
2. Với mỗi tần suất n: số cặp = n*(n-1)/2 (tổ hợp chập 2)
3. Tổng tất cả

Ví dụ minh họa

from collections import Counter

def solve(nums):
    c = Counter(nums)
    count = 0
    for n in c.values():
        count += n * (n - 1) // 2
    return count

nums = [5, 4, 5, 4, 4]
print(solve(nums))

Đầu vào

[5, 4, 5, 4, 4]

Đầu ra

4