Funcia
Lv.2arrayhashprefix-sum

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

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
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] 세 개입니다.

효율성

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

Function signature

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

Constraints

  • 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비트 정수 범위입니다.

Expected complexity

Time
O(N)
Space
O(N)

Examples

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

Hint

Hint

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

대신 누적합을 생각하세요. 구간 [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) 풀이는 효율성 테스트에서 시간 초과가 납니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.