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

Arnab Chakraborty

更新于：2020年11月26日

浏览量：135

开启您的职业生涯

完成课程获得认证

开始学习