Python程式：查詢四個列表中，四個索引組合的和小於目標值的唯一組合個數

假設我們有四個數字列表A、B、C和D，還有一個數字target。我們需要找到不同的唯一索引i、j、k、l的數量，使得A[i] + B[j] + C[k] + D[l] ≤ target。

例如，如果輸入是A = [3, 2] B = [5, 3] C = [1] D = [2, 3] target = 9，則輸出為3，因為我們可以選擇以下組合：[3, 3, 1, 2] [3, 3, 1, 2] [2, 3, 1, 3]

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

  • temp_list := 一個新的列表
  • 對於i從0到A的大小，執行：
    • 對於j從0到B的大小，執行：
      • 將(A[i] + B[j])插入到temp_list的末尾
  • 對temp_list進行排序
  • ans := 0
  • 對於i從0到C的大小，執行：
    • 對於j從0到D的大小，執行：
      • sum_cd := C[i] + D[j]
      • sum_ab := target - sum_cd
      • ans := ans + temp_list中小於等於sum_ab的元素個數
  • 返回ans

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

示例

線上演示

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

輸入

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

輸出

3

更新於：2020年11月26日

瀏覽量：135

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告