โปรแกรมค้นหาจำนวนสี่เท่าที่แตกต่างกันซึ่งสร้างผลรวมเป้าหมายใน python

สมมติว่าเรามีรายการตัวเลข A, B, C และ D สี่รายการ และยังมีค่าเป้าหมายด้วย เราต้องหาจำนวนของสี่เท่าที่แตกต่างกัน (i, j, k, l) ที่ A[i] + B[ j] + C[k] + D[l] เหมือนกับเป้าหมาย

ดังนั้น หากอินพุตเป็น A =[5, 4, 3] B =[8, 4] C =[6, 2] D =[4, 10] เป้าหมาย =23 ผลลัพธ์จะเป็น 3 ค่าสี่เท่า คือ [5, 8, 6, 4] [3, 4, 6, 10] [3, 8, 2, 10].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• นับ :=0
• m :=แผนที่ว่างเปล่า
• สำหรับแต่ละ i ใน A ทำ
  • สำหรับแต่ละ j ใน B ทำ
    • m[i + j] :=m[i + j] + 1
  • สำหรับแต่ละ k ใน C ทำ
    • สำหรับแต่ละ z ใน D ทำ
      • ถ้า (เป้าหมาย - (k + z)) อยู่ในหน่วย m แล้ว
        • นับ :=นับ + m[เป้าหมาย - (k + z)]
• จำนวนคืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

ตัวอย่าง

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))

อินพุต

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

ผลลัพธ์

3