Chương trình tìm số phần tư phân biệt tạo thành tổng mục tiêu trong python

Giả sử chúng ta có bốn danh sách các số A, B, C và D và cũng có một giá trị đích, chúng ta phải tìm số bộ tứ phân biệt (i, j, k, l) sao cho A [i] + B [ j] + C [k] + D [l] giống với mục tiêu.

Vì vậy, nếu đầu vào là A =[5, 4, 3] B =[8, 4] C =[6, 2] D =[4, 10] target =23, thì đầu ra sẽ là 3, gấp bốn lần là [5, 8, 6, 4] [3, 4, 6, 10] [3, 8, 2, 10].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• số lượng:=0
• m:=một bản đồ trống
• đối với mỗi tôi trong A, thực hiện
  • đối với mỗi j trong B, thực hiện
    • m [i + j]:=m [i + j] + 1
  • với mỗi k trong C, thực hiện
    • đối với mỗi z trong D, thực hiện
      • if (target - (k + z)) tính bằng m, thì
        • count:=count + m [target - (k + z)]
• số lần trả lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

class Solution:
   def solve(self, A, B, C, D, target):
      count = 0
      from collections import defaultdict
      from collections import Counter

      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