Chương trình đếm số bộ 4 chỉ số duy nhất tổng nhỏ hơn target từ 4 danh sách bằng Python

Cho 4 danh sách A,B,C,D và target. Đếm số bộ chỉ số (i,j,k,l) khác nhau sao cho A[i]+B[j]+C[k]+D[l] <= target.

Ví dụ: A=[3,2], B=[5,3], C=[1], D=[2,3], target=9 → 3.

Giải thuật

• Tính tất cả tổng A[i]+B[j] lưu vào temp_list, sắp xếp.
• Với mỗi cặp (C[k], D[l]): sum_cd = C[k]+D[l], sum_ab = target - sum_cd.
• Dùng bisect_right đếm số phần tử trong temp_list ≤ sum_ab.
• Cộng dồn vào kết quả.

Ví dụ minh họa

from bisect import bisect_right
class Solution:
    def solve(self, A, B, C, D, target):
        temp_list = []
        for i in range(len(A)):
            for j in range(len(B)):
                temp_list.append(A[i] + B[j])
        temp_list.sort()
        ans = 0
        for i in range(len(C)):
            for j in range(len(D)):
                sum_cd = C[i] + D[j]
                sum_ab = target - sum_cd
                ans += bisect_right(temp_list, sum_ab)
        return ans

ob = Solution()
A = [3, 2]
B = [5, 3]
C = [1]
D = [2, 3]
target = 9
print(ob.solve(A, B, C, D, target))

Đầu vào

[3, 2], [5, 3], [1], [2, 3], 9

Đầu ra

3