수들의 합 4
시간 제한2초메모리 제한128 MB
배열의 연속 부분합 중 값이 K와 같은 것의 개수를 세는 문제로, 누적합과 해시맵으로 해결합니다.
문제
정수 배열 A에는 A[1], A[2], ..., A[N]까지 N개의 정수가 들어 있다. 인덱스 i와 j가 1 <= i <= j <= N을 만족할 때, A[i]부터 A[j]까지 연속한 원소의 합을 부분합이라고 한다.
N과 배열 A가 주어질 때, 가능한 N x (N + 1) / 2개의 부분합 중 값이 K인 부분합이 몇 개인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 N과 K가 주어진다. (1 <= N <= 200,000, |K| <= 2,000,000,000) N과 K 사이에는 공백 하나가 있다.
둘째 줄에는 배열 A를 이루는 N개의 정수가 A[1], A[2], ..., A[N] 순서로 공백을 사이에 두고 주어진다. 각 정수의 절댓값은 10,000을 넘지 않는다.
출력
합이 K인 부분합의 개수를 첫째 줄에 출력한다.