Tìm dãy con có tổng bằng S (n <=2.10^6, s<=10^9)

[Aries_White]

Chào mọi người ạ! Mọi người có thể cho mình xin ý tưởng bài này không ạ?

Cho một mảng N số nguyên dương, nhiệm vụ của bạn là đếm số lượng dãy con lien tiếp có tổng bằng X.

Dữ liệu vào: File xsum1.inp gồm:

• Dòng 1: ghi hai số nguyên N và X kích thước của dãy và tổng mục tiêu X.
• Dòng 2: Ghi N số nguyên a1,a2, … ,aN là các phần tử của dãy.

Dữ liệu ra: File xsum1.out gồm duy nhất một số là số lượng dãy con có tổng bằng x.

Ràng buộc:
1 ≤ n ≤ 2*10^5
1 ≤ x,ai ≤10^9
ví dụ
Input:

5 7
2 4 1 2 7

Output:

3

[Gio (Gió)]

Dùng kĩ two pointer thôi bạn

Two Pointers Technique - GeeksforGeeks

Trong bài này thay vì tìm 1 cặp a[i], a[j] thì tính cộng dồn từ i đến j. Do a[i] > 0 nên tổng này là dãy tăng khi tăng j và giảm khi tăng i.

[kisuluoibieng (Tên Gì Cũng Được)]

Bạn đã thử làm cách tệ nhất chưa? Là cách đề ghi sao làm y như vậy, O(n^3)

[rogp10]

Rồi chừng nào xong

Bài này dùng prefix sum

[kisuluoibieng (Tên Gì Cũng Được)]

Khi người ta chưa nghĩ ra được gì thì bạn nói “prefix sum” có giúp ích được gì? Bạn đang muốn tỏ ra bạn biết giải? có quan trọng không?
học lập trình phải đi từ phương pháp đơn giản rồi mới tới những thứ như giải thuật,
ngay cả implement cái đề bài còn chưa được thì nói gì tới giải thuật ở đây?

[kienonline19 (Nguyen Kien)]

Em nghĩ ý anh @rogp10 muốn bạn ý googling thôi, không có ý gì đâu anh

[emgaiit (Nguyễn Như Quỳnh)]

Cách kém tối ưu O(n^2)

#include <iostream>
using namespace std;
int tinhKetQua(int a[], int n, int K){
    int kq = 0;
      for(int i = 0;i < n; i++){
        int sum = 0;
        for(int j = i;j<n;j++){
            sum += a[j];
            if(sum == K){
                kq++;
            }
        }
    }
    return kq;
}
int main()
{
    int kq = 0;
    int n,K;
    cin>>n>>K;
    int a[n];
    for(int i = 0;i<n;i++){
        cin>>a[i];
    }
    kq = tinhKetQua(a,n,K);
    cout<<kq;
    return 0;
}