[백준] 수들의 합4 복기

문제

https://www.acmicpc.net/problem/2982

알고리즘

누적합

시간 복잡도 O(1)로 찾기 위해서는

S[i] (누적합의 끝 인덱스) - S[j] (누적합의 시작 인덱스) = K
누적합의 시작 인덱스 S[i]를 알고 있을 때,
S[j]는 S[i] - K를 의미한다.

모든 누적합 딕셔너리에서 S[i] - K의 갯수를 카운드해서 정답에 더해준다.

코드

N, K = map(int, input().split())

lists = list(map(int, input().split()))

sums_list = dict()

sums = 0
answer = 0
for i in range(len(lists)):
    sums += lists[i]

    # 해당 누적합이 K와 같은 경우는 두가지  경우도 만족해야한다.
    #  때문에 if else문이 아닌 두개의 if문으로 작성해야한다.
    if sums - K in sums_list:
        answer += sums_list[sums-K]
    if sums == K:
        answer += 1

    if sums in sums_list.keys():
        sums_list[sums] += 1
    else:
        sums_list[sums] = 1

print(answer)