Chương trình tìm số bộ 4 chỉ số phân biệt tổng bằng target từ 4 danh sách bằng Python

Cho 4 danh sách A,B,C,D và target. Đếm số bộ (i,j,k,l) phân biệt sao cho A[i]+B[j]+C[k]+D[l] == target.

Ví dụ: A=[5,4,3], B=[8,4], C=[6,2], D=[4,10], target=23 → 3.

Giải thuật

• Tính tất cả tổng A[i]+B[j] lưu tần suất vào map m.
• Với mỗi cặp (C[k], D[l]): nếu target - (C[k]+D[l]) có trong m, cộng m[target - (C[k]+D[l])] vào kết quả.
• Phức tuyến O(|A||B| + |C||D|).

Ví dụ minh họa

class Solution:
    def solve(self, A, B, C, D, target):
        count = 0
        from collections import defaultdict
        m = defaultdict(int)
        for i in A:
            for j in B:
                m[i + j] += 1
        for k in C:
            for z in D:
                if target - (k + z) in m:
                    count += m[target - (k + z)]
        return count

ob = Solution()
A = [5, 4, 3]
B = [8, 4]
C = [6, 2]
D = [4, 10]
target = 23
print(ob.solve(A, B, C, D, target))

Đầu vào

[5, 4, 3], [8, 4], [6, 2], [4, 10], 23

Đầu ra

3