CSES - Subarray Sums II | Tổng đoạn con II

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

tan , Flower_On_Stone , Lephuchieuzz

Dạng bài

Điểm: 1000 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là đếm số lượng đoạn con có tổng \(x\).

Input

Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(x\): kích thước của mảng và tổng \(x\).
Dòng tiếp theo có \(n\) số nguyên \(a_1, a_2, \ldots, a_n\): nội dung của mảng.

Output

In một số nguyên: số lượng đoạn con được yêu cầu.

Constraints

\(1 \le n \le 2 \cdot 10^5\)
\(-10^9 \le x, a_i \le 10^9\)

Example

Sample input

5 7
2 -1 3 5 -2

Sample output

Bình luận

include <iostream>

include <vector>

include <unordered_map>

using namespace std;

int main() {
int n;
long long x;
cin >> n >> x;

vector<long long> arr(n);
for (int i = 0; i < n; ++i) {
    cin >> arr[i];
}

unordered_map<long long, int> prefix_count;
prefix_count[0] = 1; // Khởi tạo prefix_sum là 0 để bao gồm trường hợp đoạn con bắt đầu từ đầu mảng

long long prefix_sum = 0;
long long count = 0;

for (int i = 0; i < n; ++i) {
    prefix_sum += arr[i];
    long long target = prefix_sum - x;
    if (prefix_count.find(target) != prefix_count.end()) {
        count += prefix_count[target];
    }
    prefix_count[prefix_sum]++;
}

cout << count << endl;

return 0;

}

code chuẩn ae tham khảo nha

Phản hồi