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] target = 23，則輸出將為3，四元組為[5, 8, 6, 4] [3, 4, 6, 10] [3, 8, 2, 10]。

為了解決這個問題，我們將遵循以下步驟

  • count := 0
  • m := 一個空對映
  • 對於A中的每個i，執行
    • 對於B中的每個j，執行
      • m[i + j] := m[i + j] + 1
    • 對於C中的每個k，執行
      • 對於D中的每個z，執行
        • 如果(target - (k + z))在m中，則
          • count := count + m[target - (k + z)]
  • 返回count

讓我們看看下面的實現，以便更好地理解

示例

線上演示

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

更新於: 2020年11月26日

309 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告