정수 값으로 구성된 4개의 목록 A, B, C, D가 있다고 가정하면 A[i ] + B[j] + C[k] + D[l]은 0입니다. 모든 A, B, C, D가 0 ≤ N ≤ 500인 동일한 길이의 N을 갖는다고 가정합니다. 모든 정수는 -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에 대해
- B
- 의 각 요소 j에 대해
- i + j가 sums 맵에 없으면 sums[i + j] :=1로 설정
- 그렇지 않으면 sum[i + j]의 값을 늘립니다.
- B
- 카운터:=0
- C
- 의 각 요소 i에 대해
- D
- 의 각 요소 j에 대해
- 합계가 (-1)*(i + j)이면 counter :=counter + sums[-1 * (i + j)]
- D
- 반품 카운터
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
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