Skip to main content

Practice · 2 of 5

Đếm đoạn con có tổng bằng K

CHALLENGE
Difficulty: intermediate+25 XP

**Bài toán.** Mảng n phần tử NGUYÊN (−10^9 ≤ a[i] ≤ 10^9) và số K. Đếm số đoạn con liên tiếp có tổng đúng bằng K. **Ràng buộc:** 1 ≤ n ≤ 2·10^5; |K| ≤ 10^9. Số cách có thể lên tới n(n+1)/2 — dùng long long. Số âm xuất hiện → cửa sổ trượt SAI (tổng không đơn điệu). Tiền tố P + map đếm "số tiền tố cũ có giá trị P_hiện − K" — O(n) dự kiến.

Back to lesson: Practice: Synthesis Problem Set