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

Trung bình

mảngtổng tiền tốhash map6 test · 3 giây

Cho dãy n số nguyên (có thể âm) và số K. Đếm số đoạn con liên tiếp có tổng đúng bằng K.

Gợi ý: tổng đoạn (i, j] = P[j] − P[i]. Đếm xem bao nhiêu P[i] = P[j] − K bằng hash map.

Dữ liệu vào

Dòng 1: n K (1 ≤ n ≤ 2·10⁵, |K| ≤ 10⁹).

Dòng 2: n số nguyên (|aᵢ| ≤ 10⁴).

Số đoạn con (có thể vượt 32-bit).

Input

5 3
1 2 1 2 1

Output

Các đoạn [1,2], [2,1], [1,2], [2,1]

Input

3 0
0 0 0

Output

6 đoạn con đều có tổng 0

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.