โปรแกรมนับจำนวน Triplets ที่ดี (Good Triplets) ใน Python

ภาพรวม

Triplet (nums[i], nums[j], nums[k]) เรียกว่า "ดี" ถ้า:

• 0 <= i < j < k < len(nums)
• |nums[i] - nums[j]| <= a
• |nums[j] - nums[k]| <= b
• |nums[i] - nums[k]| <= c

ต้องการนับจำนวน Triplets ที่ดีทั้งหมด

ตัวอย่าง

nums = [5,2,3,3,12,9], a=7, b=2, c=3

Triplets ที่ดี: [(5,2,3), (5,2,3), (5,3,3), (2,3,3)] → รวม 4 คู่

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

1. ตั้งค่า res = 0
2. วนลูป i จาก 0 ถึง n-1
3. วนลูป j จาก i+1 ถึง n-1
4. วนลูป k จาก j+1 ถึง n-1
5. ตรวจสอบเงื่อนไขทั้ง 3 ข้อ ถ้าผ่าน ให้ res += 1
6. คืนค่า res

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

def solve(nums, a, b, c):
    res = 0
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                if abs(nums[i] - nums[j]) <= a and \
                   abs(nums[j] - nums[k]) <= b and \
                   abs(nums[i] - nums[k]) <= c:
                    res += 1
    return res

nums = [5,2,3,3,12,9]
a, b, c = 7, 2, 3
print(solve(nums, a, b, c))

อินพุต

[5,2,3,3,12,9], 7, 2, 3

เอาต์พุต

4

ความซับซ้อน

• เวลา: O(n³) - ใช้ได้กับ n เล็ก (n ≤ 100)
• พื้นที่: O(1)