Python中的4Sum II

假设我们有四个整数值的列表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

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

• 制作一张称为求和的映射

• 对于A中的每个元素

• 如果i + j不在求和图中，则设置sums [i + j]：= 1

• 否则增加和的值[i + j]

• 对于B中的每个元素j

• 计数器：= 0

• 对于C中的每个元素

• 如果(-1)*（i + j）相加，则counter：= counter + sums [-1 *（i + j）]

• 对于D中的每个元素j

• 返回柜台

示例

让我们看下面的实现以更好地理解-

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