Python 中的 4Sum II

pythonserver side programmingprogramming更新于 2025/10/31 13:00:17

假设我们有四个整数值列表 A、B、C、D，我们必须计算有多少个元组 (i、j、k、l)，使得 A[i] + B[j] + C[k] + D[l] 为零。假设所有 A、B、C、D 的长度均为 N，其中 0 ≤ N ≤ 500。请记住，所有整数都在 -228 到 228 - 1 的范围内，并且保证结果最多为 231 - 1。因此，如果输入为 A = [1, 2]、B = [-2, -1]、C = [-1, 2]、D = [0, 2]，则输出将为 2。这是因为有两个元组，它们是 (0, 0, 0, 1)，所以 A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0，另一个元组是 (1, 1, 0, 0)，A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

为了解决这个问题，我们将遵循以下步骤 −

创建一个名为 sums 的映射
对于 A 中的每个元素 i
- 对于 B 中的每个元素 j
  - 如果 i + j 不在 sums 映射中，则设置 sums[i + j] := 1
  - 否则增加 sums[i + j] 的值
counter := 0
对于 C 中的每个元素 i
- 对于 D 中的每个元素 j
  - 如果 sums 中有 (-1)*(i + j)，则 counter := counter + sums[-1 * (i + j)]
返回 counter

示例

让我们看看以下实现以获得更好的理解 −

class Solution(object):
   def fourSumCount(self, A, B, C, D):
      sums ={}
      for i in A:
         for j in B:
            if i+j not in sums:
               sums[i+j] = 1
            else:
               sums[i+j] +=1
      counter = 0
      for i in C:
         for j in D:
            if -1 * (i+j) in sums:
               #print(-1 * (i+j))
               counter+=sums[-1*(i+j)]
      return counter
ob1 = Solution()
print(ob1.fourSumCount([1,2], [-2,-1], [-1,2], [0,2]))