mycode 过不了。。。我也不知道为什么。。。
class Solution(object):
def fourSumCount(self, A, B, C, D):
"""
:type A: List[int]
:type B: List[int]
:type C: List[int]
:type D: List[int]
:rtype: int
"""
def deal(i,j,k,l):
if [i,j,k,l] not in self.record:
self.record.append([i,j,k,l])
else:
return
#print(self.res,i,j,k,l)
if i < I and j < J and k < K and l < L:
if A[i] + B[j] + C[k] + D[l] == 0:
self.res += 1
print(self.res,i,j,k,l)
elif A[i] + B[j] + C[k] + D[l] < 0:
deal(i,j,k,l+1)
deal(i,j,k+1,l)
deal(i,j+1,k,l)
deal(i+1,j,k,l)
else:
return
else:
return A,B,C,D = sorted(A),sorted(B),sorted(C),sorted(D)
i,j,k,l = 0,0,0,0
I,J,K,L = len(A),len(B),len(C),len(D)
self.res = 0
self.record = []
deal(i,j,k,l)
return self.res
参考
class Solution(object):
def fourSumCount(self, A, B, C, D):
"""
:type A: List[int]
:type B: List[int]
:type C: List[int]
:type D: List[int]
:rtype: int
""" from collections import Counter
dicA , dicB ,dicC ,dicD = Counter(A), Counter(B), Counter(C), Counter(D)
res = 0
dic = {}
for a , a_nember in dicA.items():
for b , b_nember in dicB.items():
dic[a+b] = dic.get(a+b,0) + a_nember * b_nember
#例如2+(-1)=1,而A中2的数量*B中-2的数量+B中2的数量*A中-2的数量就等于A和B中元素和为1的组合数
for c, c_nember in dicC.items():
for d, d_nember in dicD.items():
res += dic.get(-c-d,0) * c_nember * d_nember
return res