LeetCode 560 - Subarray Sum Equals K (Medium)

출처: https://leetcode.com/problems/subarray-sum-equals-k/

// LeetCode 560 - Subarray Sum Equals K (Medium)
// https://leetcode.com/problems/subarray-sum-equals-k/

// 문제 설명
// 정수 배열 nums와 정수 k가 주어질 때,
// 합이 정확히 k인 연속 부분배열(subarray)의 총 개수를 반환하라.

// 제약 조건
// 1 <= nums.length <= 2 * 10^4
// -1000 <= nums[i] <= 1000
// -10^7 <= k <= 10^7

// Example 1
// Input : nums = [1,1,1], k = 2
// Output: 2   ([1,1] 두 개)
//
// Example 2
// Input : nums = [1,2,3], k = 3
// Output: 2   ([1,2], [3])

// 접근 — 프리픽스 합 + 해시맵(등장 횟수 카운팅)
// 음수가 있어 슬라이딩 윈도우 불가(윈도우를 줄여도 합이 커질 수 있음). 완전 탐색은 O(n^2).
// 구간 [i..j]의 합이 k  ⇄  p[j] - p[i-1] = k  ⇄  p[i-1] = p[j] - k.
// 1) 누적합 s를 왼쪽부터 흘리며 "누적합 값 → 지금까지 등장 횟수"를 해시맵 cnt에 기록.
// 2) 각 위치에서 cnt[s - k]를 답에 더한다 — 현재 위치에서 끝나는 정답 구간의 개수.
// 3) cnt[0] = 1 로 시작(빈 접두사) — 배열 처음부터 시작하는 구간을 자동 포함.
// 시간 평균 O(n), 공간 O(n)

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    int subarraySum(vector<int>& nums, int k)
    {
        unordered_map<int, int> cnt;                  // 누적합 값 → 등장 횟수
        cnt[0] = 1;                                   // 빈 접두사

        int s = 0, answer = 0;
        for (int x : nums)
        {
            s += x;
            auto it = cnt.find(s - k);                // 나보다 k 작은 누적합이 몇 번 나왔나
            if (it != cnt.end()) answer += it->second;
            ++cnt[s];                                 // 등록은 조회 뒤 — k=0일 때 자기 자신 중복 방지
        }
        return answer;
    }
};

정리

• 어제 303의 프리픽스 합에서 한 단계 발전형. 구간 조건 p[j] - p[i-1] = k를 “내 왼쪽에 p[j] - k라는 누적합이 몇 번 나왔나”로 뒤집는 것이 핵심이다. 존재 여부가 아니라 개수를 물으므로 set이 아닌 unordered_map<누적합, 횟수>를 쓴다 — 회사에 있는 사람(7785)에서 map을 플래그로 쓰던 것의 카운터 버전.
• 음수 원소 때문에 슬라이딩 윈도우가 성립하지 않는다. 윈도우를 넓힌다고 합이 단조 증가하지 않아 “합이 크면 줄이고 작으면 늘린다”는 판단 자체가 불가능하다. 원소가 전부 양수라면 투 포인터로도 풀린다 — 조건(음수 허용 여부)이 풀이 계열을 가르는 문제.
• cnt[0] = 1(빈 접두사)은 303에서 p[0] = 0을 두던 것과 같은 역할이다. 이게 없으면 배열 맨 앞부터 시작하는 정답 구간(p[j] == k인 경우)이 통째로 빠진다.
• 순서 함정: 현재 누적합의 등록(++cnt[s])은 반드시 조회 뒤에 해야 한다. 먼저 등록하면 k = 0일 때 자기 자신(길이 0 구간)을 세어버린다.
• 조회에 operator[] 대신 find()를 쓴 이유 — cnt[s - k]는 없는 키를 0으로 만들어 삽입해버려서(std::map의 operator[] 함정과 동일) 맵이 불필요하게 커진다. unordered_map은 평균 O(1)이지만 해시 충돌 시 최악 O(n)이라는 것까지가 어제 면접 복기(RBT vs 해시)와 이어지는 지점.
• 검증: 예제 2개(2, 2)에 더해 음수·0 포함 케이스 [1,-1,0], k=0 → 3, [-1,-1,1], k=0 → 1 통과 (MSVC /std:c++17 컴파일·실행).