Funcia
Lv.2arrayhashprefix-sum

합이 K인 연속 부분배열의 개수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

정수 배열 A와 정수 K가 주어집니다. 원소에 음수가 섞여 있을 수 있습니다.

합이 정확히 K인 연속 부분배열의 개수를 반환하세요.

입출력 예

AKresult
[1, 2, 3]32
[1, -1, 0]03
[3, 4, 7, 2, -3, 1, 4, 2]74

입출력 예 설명

예 1 — [1, 2]와 [3] 두 개입니다.

예 2 — [1, -1], [0], [1, -1, 0] 세 개입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(A: int[], K: long) → long

제한 사항

  • 1≤N≤200,0001 \le N \le 200{,}000
  • −109≤A[i]≤109-10^9 \le A[i] \le 10^9
  • −1018≤K≤1018-10^{18} \le K \le 10^{18}
  • 개수는 64비트 정수 범위입니다.

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

AK기대 출력
[1,2,3]32
[1,-1,0]03
[3,4,7,2,-3,1,4,2]74

힌트

힌트

음수가 섞여 있어 슬라이딩 윈도우를 쓸 수 없습니다. 창문을 늘려도 합이 단조롭게 늘지 않기 때문입니다.

대신 누적합을 생각하세요. 구간 [l,r][l, r]의 합이 KK라는 건

prefix[r+1]−prefix[l]=K⟺prefix[l]=prefix[r+1]−K\text{prefix}[r+1] - \text{prefix}[l] = K \quad\Longleftrightarrow\quad \text{prefix}[l] = \text{prefix}[r+1] - K

입니다. 그러니 왼쪽에서 오른쪽으로 누적합을 굴리면서, 과거에 현재합 - K가 몇 번 나왔는지를 해시맵에서 꺼내 더하면 됩니다.

주의할 점 두 가지입니다.

  • 맵을 {0: 1}로 초기화하세요. 배열 맨 앞부터 시작하는 구간을 세기 위한 "아무것도 안 더한 상태"입니다.
  • 매 단계에서 조회를 먼저, 기록을 나중에 하세요. 순서가 바뀌면 자기 자신이 짝으로 세어집니다.

복잡도 목표

모든 구간을 확인하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251400 ms추정
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1000 ms도출됨

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4011판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.