4Sum II 以 Python 编写

假设我们有四个包含整数值的列表 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
      • 如果 sums 映射中不存在 i + j，则设置 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]))

输入

[1,2]
[-2,-1]
[-1,2]
[0,2]

输出

2

更新于: 2020 年 4 月 28 日

679 次浏览

开启您的 职业生涯

完成课程并获得认证

开始
广告