[LeetCode][JAVA] 560. Subarray Sum Equals K

💡 문제
560. Subarray Sum Equals K (https://leetcode.com/problems/subarray-sum-equals-k/submissions/1763406903/?source=submission-noac)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• Prefix Sum(누적합): prefix[i] = nums[0] + ... + nums[i]
• 구간합 공식: sum(l..r) = prefix[r] - prefix[l-1]
• 해시맵 카운팅: 지금까지 등장한 누적합 값의 빈도를 Map<sum, count>로 관리

---

🤓 문제 풀이

인덱스 r까지의 누적합을 prefix라 하면, 합이 k인 서브어레이 (l..r) 존재 조건은
prefix[l-1] = prefix[r] - k.
따라서 현재 prefix에서 (prefix - k)가 과거에 몇 번 있었는지를 누적해 가면 정답.

초기값으로 cnt.put(0, 1)을 넣어 l=0(시작부터 r까지의 합이 k인 경우)도 자연 처리.

🔨 문제 설명

• 입력: 정수 배열 nums, 정수 k
• 출력: 합이 k인 연속 부분 배열의 개수

예)

• [1,1,1], k=2 → 2
• [1,2,3], k=3 → 2

제약

• 1 <= nums.length <= 2*10^4
• -1000 <= nums[i] <= 1000, -10^7 <= k <= 10^7

---

🔨 접근 방법

1. cnt 맵에 누적합의 등장 횟수 저장 (cnt.put(0,1)로 시작).
2. 배열을 왼→오로 순회하며 prefix += nums[i].
3. 지금까지의 데이터에서 합이 k가 되는 시작점 개수 = cnt.getOrDefault(prefix - k, 0) → 정답에 더함.
4. 현재 prefix를 cnt에 반영: cnt[prefix]++.

음수/0 허용이라 투 포인터로는 안 된다(구간을 단조롭게 늘리거나 줄인다고 합이 단조 변하지 않음).

---

🔨 문제 풀이 과정

예) nums=[1,1,1], k=2

• 시작: cnt={0:1}, prefix=0, ans=0
• i=0: prefix=1, prefix-k=-1의 빈도는 0 → ans=0, cnt[1]++
• i=1: prefix=2, prefix-k=0의 빈도는 1 → ans=1, cnt[2]++
• i=2: prefix=3, prefix-k=1의 빈도는 1 → ans=2, cnt[3]++
• 결과 2

---

🔨 구현코드

package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. Subarray Sum Equals K
 * - 해시맵 기반 Prefix Sum 카운팅
 * - 시간복잡도 O(n), 공간복잡도 O(n)
 */
public class LeSolution07 {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;

        Map<Integer, Integer> cnt = new HashMap<>();
        cnt.put(0, 1); // prefix == k 인 (0..r) 구간 처리용

        int prefix = 0;
        int ans = 0;

        for (int x : nums) {
            prefix += x;
            // prefix[r] - prefix[l-1] = k => prefix[l-1] = prefix[r] - k
            ans += cnt.getOrDefault(prefix - k, 0);
            // 현재 prefix 반영
            cnt.put(prefix, cnt.getOrDefault(prefix, 0) + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        LeSolution07 sol = new LeSolution07();
        System.out.println(sol.subarraySum(new int[]{1,1,1}, 2));   // 2
        System.out.println(sol.subarraySum(new int[]{1,2,3}, 3));   // 2
        System.out.println(sol.subarraySum(new int[]{1,-1,0}, 0));  // 3
        System.out.println(sol.subarraySum(new int[]{0,0,0}, 0));   // 6
        System.out.println(sol.subarraySum(new int[]{-1,-1,1}, 1)); // 1
    }
}

---

📚 풀이 보완

코드 설명

• cnt.put(0,1): 시작점이 0인 구간을 세기 위한 필수 전처리.
• ans += cnt.getOrDefault(prefix - k, 0): 현재 r에서 가능한 모든 l의 개수를 한 번에 합산.
• 마지막에 cnt[prefix]++: 다음 r에 대비해 현재 누적합을 기록.
• cnt.put(prefix, cnt.getOrDefault(prefix + k, 0) + 1) 같은 오타(※ 주석의 잘못된 라인)
  → 반드시 cnt.getOrDefault(prefix, 0) + 1 이어야 함.
• 투 포인터 시도: 음수가 있으면 실패. 반드시 누적합+맵으로.

---

📍 Plus+

 

• 대안(브루트포스): 모든 (l,r)을 시도하면 O(n^2) → n=2e4에서 시간초과.
• 자료형: 제약상 int로 충분(최대 절댓값 ≈2e7). 더 큰 입력이면 long 고려.

 

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

시간: O(n) — 한 번 순회하며 해시 조회/갱신은 평균 O(1)
공간: O(n) — 서로 다른 누적합 값 개수만큼 맵 사용

 

 

• 핵심 공식: sum(l..r) = prefix[r] - prefix[l-1]
• 전략: 현재 prefix에서 (prefix - k)의 과거 빈도만큼 정답 누적
• 복잡도: 시간 O(n), 공간 O(n)

 

---

풀이 참고 로직

• 초기화: cnt = {0:1}, prefix=0, ans=0
• 루프: prefix += x; ans += cnt[prefix - k]; cnt[prefix]++