โปรแกรมนับจำนวน Good Pairs ในอาร์เรย์ Python

ภาพรวม

Good Pair คือคู่ดัชนี (i, j) ที่ nums[i] == nums[j] และ i < j ต้องการนับจำนวน Good Pairs ทั้งหมด

ตัวอย่าง

nums = [5,6,7,5,5,7]

Good Pairs: (0,3), (0,4), (3,4), (2,5) → รวม 4 คู่

ขั้นตอนการแก้ปัญหา (Brute Force)

1. ตั้งค่า count = 0
2. วนลูป i จาก 0 ถึง n-1
3. วนลูป j จาก i+1 ถึง n-1
4. ถ้า nums[i] == nums[j] ให้ count += 1
5. คืนค่า count

ตัวอย่างโค้ด (Python)

def solve(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] == nums[j]:
                count += 1
    return count

nums = [5,6,7,5,5,7]
print(solve(nums))

อินพุต

[5,6,7,5,5,7]

เอาต์พุต

4

วิธีปรับปรุง (Optimized)

ใช้ Dictionary นับความถี่ของแต่ละค่า ถ้าค่าใดมีความถี่ f จะมี Good Pairs = f * (f-1) // 2 คู่ ลดเวลาจาก O(n²) เป็น O(n)

from collections import Counter
def solve_optimized(nums):
    freq = Counter(nums)
    return sum(v * (v-1) // 2 for v in freq.values())