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 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告