Dùng mảng cộng dồn (prefix sum) kết hợp với bảng băm (hashmap).

Gọi \(pref[i]\) là tổng \(a_1 + ... + a_i\). Đoạn \((l, r)\) có tổng bằng \(K\) khi và chỉ khi \(pref[r] - pref[l-1] = K\), hay \(pref[l-1] = pref[r] - K\).

Duyệt từ trái sang phải, với mỗi \(pref[r]\), kiểm tra xem \(pref[r] - K\) đã xuất hiện bao nhiêu lần.

Độ phức tạp \(O(N)\).

Hướng dẫn giải

Sử dụng thuật toán phù hợp để giải quyết bài toán.

Mã nguồn C++

// Giải thuật ps cho bài toán ps-sub-sum-k\n#include <bits/stdc++.h>
using namespace std;

int main() {
    // Doc du lieu dau vao
    ios::sync_with_stdio(0); cin.tie(0);
    // TODO: implement solution
    cout << "\n";
    return 0;
}