[Prefix Sums] 560. Subarray Sum Equals K ★★★★★

560. Subarray Sum Equals K

 

누적합 + 해시맵을 사용하는 대표적인 패턴 문제입니다.

---

✅ 문제 요약

• 배열 nums와 정수 k가 주어질 때,
  연속된 구간(subarray)의 합이 k가 되는 경우의 수를 구하라.

 

from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        count = 0                          # 정답: 합이 k인 서브어레이의 개수
        prefixSum = 0                      # 누적합 (0부터 현재 인덱스까지의 합)
        prefixCount = defaultdict(int)     # key: 누적합, value: 그 누적합이 몇 번 나왔는지 저장

        prefixCount[0] = 1  # ❗️ 중요 포인트 ❗️
        # 누적합이 k인 서브어레이가 [0:i] 범위일 때를 처리하려면
        # prefixSum - k == 0 이 되어야 하고,
        # 그 0이 prefixCount에 있어야 count += 1 이 가능해짐
        # 즉, 아무것도 더하지 않은 상태에서 0이라는 누적합이 한 번 있었던 셈!

        for num in nums:
            prefixSum += num  # 현재까지의 누적합 계산

            # prefixSum - k가 과거에 몇 번 나왔는지를 확인
            # 그 횟수만큼 (과거에 그런 누적합이 있었던 시점 이후부터 지금까지의) 부분합이 k라는 의미
            count += prefixCount[prefixSum - k]

            # 현재 누적합을 prefixCount에 기록
            # (다음에 나올 수 있는 prefixSum - k 체크를 위해)
            prefixCount[prefixSum] += 1

        return count

 

✅ 직관적 흐름 정리

1. prefixSum = 지금까지 합
2. prefixSum - k = 과거에 이 값이 있었다면 → 그 이후부터 지금까지의 합은 k
3. prefixCount[prefixSum - k] = 그 과거 누적합이 몇 번 있었는지
4. 그만큼 count에 더함

https://youtu.be/fFVZt-6sgyo

 

1. Brute Force

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = 0
        for i in range(len(nums)):
            sum = 0
            for j in range(i, len(nums)):
                sum += nums[j]
                if sum == k:
                    res += 1
        return res

 

Time & Space Complexity

• Time complexity: O(n^2)
• Space complexity: O(1)

 

2. Hash Map

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        res = curSum = 0
        prefixSums = { 0 : 1 }

        for num in nums:
            curSum += num
            diff = curSum - k

            res += prefixSums.get(diff, 0)
            prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)
        
        return res

 

Time & Space Complexity

• Time complexity: O(n)
• Space complexity: O(n)