누적합

560. Subarray Sum Equals K

리트코드 누적합 문제다

처음에는 for문 돌려서 모든 합을 구하고, 또 거기서 기존 누적합 결과들을 하나하나 빼는 방식을 생각했는데 아래와 같은 방법을 이용하면 O(n)만에 풀 수 있다.

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dict={0: 1}
        res=0
        pr = 0
        for no in nums:
            pr +=no
            if pr-k in dict:
                res += dict[pr-k]
            if pr not in dict:
                dict[pr] = 1
            else:
                dict[pr]+=1
        return res

누적합 변수 pr 에 nums 요소를 하나하나 돌리며 더해줘 누적합을 만든다

그리고 누적합 - 목표값 이 딕셔너리에 있는지 본다 . 과거의 누적합으로 이 값이 나온 적 있었다면 값이 있을 것이고, 이 횟수를 res에 더해준다. 

그리고 현재 누적합 값이 딕셔너리에 없다면 1을 넣어주고, 있다면 횟수를 1 증가시킨다.