Chương trình đếm số bộ ba tốt trong Python

Cho mảng nums và ba số nguyên a, b, c. Bộ ba (nums[i], nums[j], nums[k]) được gọi là tốt nếu:

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

Đếm số bộ ba tốt.

Ví dụ: nums = [5,2,3,3,12,9], a=7, b=2, c=3 → 4 bộ ba: [(5,2,3), (5,2,3), (5,3,3), (2,3,3)].

Thuật toán

• Khởi tạo res = 0.
• Ba vòng lặp lồng nhau i, j, k với i < j < k.
• Kiểm tra ba điều kiện giá trị tuyệt đối, nếu thỏa mãn tăng res.
• Trả về res.

Ví dụ (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 = 7
b = 2
c = 3
print(solve(nums, a, b, c))

Đầu vào

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

Đầu ra

4