핵심

• 누적합

• 해시맵

• 인덱스가 1부터 시작한다고 했을 때 1부터 N까지의 누적합을 담아놓는다

• 이후 부분합을 체크할 때 현재 위치를 currentIdx라고 하자

  • 그러면 accSum[currentIdx] - accSum[?] = K가 되는 ?의 index 수를 찾으면 된다
  • 이 개수를 HashMap에 저장함으로서 O(1)만에 찾을 수 있도록 해줌

• 1~N까지 확인할 때 순차적으로 체크 안하고 visit을 통해 경우의 수로 따지려다가 오래걸렸다

코드

package Baekjoon;

import java.io.*;
import java.util.*;
public class Algo2015 {

    static int N,K;
    static int[] accSum;
    static Map<Integer, Integer> nums = new HashMap<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        accSum = new int[N+1];

        for(int i=1; i<=N; i++) {
            accSum[i] = accSum[i-1] + Integer.parseInt(st.nextToken());
        }
        long result = 0;

        for(int start=1; start<=N; start++) {
            nums.put(accSum[start-1], nums.getOrDefault(accSum[start-1],0)+1);
            int base = accSum[start];
            int toFind = base-K;
            result += nums.getOrDefault(toFind, 0);
        }

        System.out.println(result);
    }
}