[Algorithm][LeetCode 560] Subarray Sum Equals K 문제 풀이 - 누적합과 Hash Map 활용법

🟢 LeetCode 560. Subarray Sum Equals K 문제 풀이 (with 누적합 + 해시맵)

최근 Leetcode 2845. Count of Interesting Subarrays 문제를 풀다가 막히는 부분이 있었는데, 유튜브에서 힌트를 찾아보다가 아래 영상을 발견했습니다.

How to solve Count of Interesting Subarrays (Leetcode 2845)

이 영상에서는 Leetcode 560번과 523번 문제를 먼저 풀어보면 이해가 잘 된다고 추천하더라고요.
그래서 먼저 Leetcode 560. Subarray Sum Equals K 문제를 풀어보았습니다.

---

🟢 문제 설명

Given an array of integers nums and an integer k,
return the total number of subarrays whose sum equals to k.

• Subarray: 연속된 요소들의 부분 배열 (비어 있으면 안 됨).
• Example 1:

  Input: nums = [1,1,1], k = 2
  Output: 2
  

• Example 2:

  Input: nums = [1,2,3], k = 3
  Output: 2
  

• Constraints:

  1 <= nums.length <= 2 * 10⁴
  -1000 <= nums[i] <= 1000
  -10⁷ <= k <= 10⁷
  

---

🟠 접근 방법 (총 3가지)

1️⃣ Brute Force 방식 (O(N²), O(1))

가장 직관적인 방법입니다.
모든 subarray를 하나하나 확인하면서 합이 k인 경우를 세는 방식입니다.

const subarraySum = function(nums, k) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum === k) count++;
        }
    }
    return count;
}

• 시간 복잡도: O(N²)
• 공간 복잡도: O(1)

❌ 배열이 길어질수록 매우 느려집니다.

---

2️⃣ Prefix Sum + 2중 루프 (O(N²), O(N))

누적합(Prefix Sum)을 먼저 계산해두고,
구간합을 prefixSum[i] - prefixSum[j]로 구하는 방식입니다.

const subarraySum = function(nums, k) {
    let prefix = 0;
    let count = 0;

    const preCalculatedSum = nums.map((num) => {
        prefix += num;
        return prefix;
    });

    for (let i = 0; i < preCalculatedSum.length; i++) {
        if (preCalculatedSum[i] === k) {
            count++;
        }
        for (let j = 0; j < i; j++) {
            if (preCalculatedSum[i] - preCalculatedSum[j] === k) {
                count++;
            }
        }
    }

    return count;
};

• 시간 복잡도: O(N²)
• 공간 복잡도: O(N)

⚠️ Brute Force보다는 중복 계산이 줄었지만, 시간 복잡도는 그대로입니다.

---

3️⃣ Prefix Sum + Hash Map (O(N), O(N)) ⭐️

이 문제의 최적화된 접근 방식입니다.

✅ 핵심 아이디어

• 구간합은 누적합의 차이로 알 수 있습니다.
• 구간 [i, j]의 합 = prefixSum[j] - prefixSum[i - 1]
• 이 공식을 변형하면:

  prefixSum[j] - k = prefixSum[i - 1]
  

• 현재까지 누적합이 prefixSum[j]인데,
  과거에 prefixSum[i - 1]이라는 누적합이 있었다면, 그 구간합은 k가 됩니다.
• 이전 누적합을 Hash Map에 저장해두고,
  매 순간 prefixSum[j] - k가 과거에 있었는지 빠르게 확인하면 됩니다.

🟡 prefixSum[-1] = 0을 1로 가정하는 이유

• 아무 숫자도 고르지 않고 더하지 않은 상태를 prefixSum[-1] = 0이라고 가정합니다.
• 예시: nums = [1, -1, 0], k = 0
• 합이 0이 되는 subarray:
  1. [1, -1]
  2. [1, -1, 0]
  3. [0]
• 이처럼 맨 앞에서 시작하는 구간을 구하려면,
  prefixSum[-1] = 0이라는 지점이 있어야 합니다.
• 그래서 초기 설정으로 map.set(0, 1)을 해줍니다.

🟢 코드

const subarraySum = function(nums, k) {
    const map = new Map();
    map.set(0, 1); // prefixSum[-1] = 0을 1번 있다고 가정

    let sum = 0;
    let count = 0;

    for (let num of nums) {
        sum += num;
        const target = sum - k;
        if (map.has(target)) {
            count += map.get(target); // 이전에 나왔던 target만큼 count 증가
        }
        map.set(sum, (map.get(sum) || 0) + 1); // 현재 prefix sum 저장
    }

    return count;
};

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

✅ 누적합을 이용하면서, 과거 누적합을 Map으로 관리해서 빠르게 구간합을 찾는 방식입니다.

---

🟠 정리

방법	시간 복잡도	공간 복잡도	특징
Brute Force	O(N²)	O(1)	단순하고 직관적이지만 느림
Prefix Sum + 2중 루프	O(N²)	O(N)	누적합 사용, 중복 계산 일부 감소
Prefix Sum + Hash Map (추천)	O(N)	O(N)	최적화된 방식, 실무에서도 자주 사용

---

🧭 마무리

이 문제를 통해:

• 누적합(Prefix Sum)
• Hash Map을 이용한 구간합 최적화

개념을 연습할 수 있었습니다.

이제 이 문제를 기반으로,
Leetcode 2845. Count of Interesting Subarrays 문제도 조금 더 이해하기 쉬워질 것 같습니다.

---

✅ 함께 보면 좋은 문제

• Leetcode 523. Continuous Subarray Sum (이 문제도 누적합 + 나머지 활용)