구간 합(Prefix sum) 의 응용 (부분 배열의 합 A 찾기)

코드포스 문제를 풀어보는 도중 구간합을 약간 응용한 문제를 발견했다.

https://codeforces.com/contest/1915/problem/E

 

배열 A의 구간 합 S에서 S[X]=S[Y]라면, A[x+1] 부터 A[y] 까지의 합은 0이다.

 

이유 설명

두 구간 합 S(X) 와 S(Y) 를 풀어쓰면 (X<Y) :

 

 

S(Y) - S(X) = 0 을 풀어쓰면 :

 

 

 

이것을 이용해서 부분 배열의 합이 0인 부분이 있는 지 O(N)에 찾을 수 있다.

map 또는 unordered_map 을 이용해서 값 X를 저장하고,

X가 이미 존재한다면 부분 배열의 합이 0인 부분이 존재한다는 것을 알 수 있다.

 

 

이것을 이용해서 부분 배열의 합이 A인 부분이 있는 지도 확인할 수 있다.

S(Y)-S(X) = A라면,