합계가 0 인 모든 인접한 하위 배열 계산하기

Question

길이가 n 인 임의의 숫자 (양수 및 음수)의 배열이 주어진다면, sum이 0 인 숫자 연속적인 하위 배열이 필요합니다.

예 : I는 서브 어레이는 다음과 같이되기 때문에 배열 a={1, -1 ,2 , -2, 6, -6}가 출력 6 될 것이다가 주어지면 :

1 -1 & 2 -2 & 6 -6 & 1 -1 2 -2 & 2 -2 6 -6 & 1 -1 2 -2 6 -6 

난 (N^2), I는 임의의 원하는 억지 용액 O 알고 다른 솔루션 O (n) 또는 O (n log n)?

Answer 1

배열을 a1, ..., an이라고합시다. s0, ..., sn을 sj = a1 + ... + aj (그리고 s0 = 0)에 의해 정의 된 접두사 합이라고하자. i에서 j까지의 부분 배열의 합은 sj-si-1입니다. O (n)/O (n log n) 시간 알고리즘의 경우지도를 사용하여 접두어 합계 중에서 각 번호의 발생 횟수를 계산합니다. 합계 k는이지도의 값에서 k에 대해 2를 선택합니다. 예를 들어

, 우리는 당신의 배열이있는 경우

1 -1 2 -2 6 -6 

다음 접두사 합계가

0 1 0 2 0 6 0 

하며 카운트

0: 4 
1: 1 
2: 1 
3: 1 

이며, 출력은 + 2를 선택 4 1을 선택 2 + 1 2 + 1을 선택 2 = 6 (여기서 k는 2 = k (k-1)/2를 선택). 파이썬

:

가

def countsumzero(lst): 
    prefixsums = [0] 
    for x in lst: 
     prefixsums.append(prefixsums[-1] + x) 
    freq = {} 
    for y in prefixsums: 
     if y in freq: 
      freq[y] += 1 
     else: 
      freq[y] = 1 
    return sum(v*(v-1) // 2 for v in freq.values())