Code đếm số lượng dãy con có tổng bằng k bị Time Limit Exceeded

[Duc_Khai_Tong (da sun kid)]

Cho một dãy số A gồm n số nguyên và một số nguyên k. Một dãy con gồm các phần tử liên tiếp trong A có tổng các phần tử bằng k được gọi là dãy con k. Đếm số lượng dãy con k của dãy A.

#include <stdio.h>
#include <map>
using namespace std;
map <int, int> hm;
map <int, int>:: iterator it;
int sum_of_elements(int a[], int i, int j)
{
    int sum=0;
    for(int index=i; index<i+j; index++) sum+=a[index];
    return sum;
}
void count_subarray(int a[], int n, int k)
{
    for(int j=1; j<=n; j++)
        for(int i=0; i<n-j+1; i++)
        hm[sum_of_elements(a, i, j)]++;
    for (it = hm.begin(); it != hm.end(); it++)
        if(it->first == k) printf("%d", it->second);
}
main()
{

    int n, k;
    scanf("%d", &n); scanf("%d", &k);
    int a[n];
    for(int i=0; i<n; i++)
    {
        scanf("%d", &a[i]);
    }
    count_subarray(a, n, k);
}

Code của mình bị TLE (Time Limit Exceeded) với case lớn. Mọi người có ý tưởng nào tối ưu hơn không?

[noname00 (HK boy)]

Dùng tổng tiền tố. Nếu mảng toàn số dương/âm thì tiếp tục áp dụng chặt nhị phân, nếu không thì dùng map.

Thuật toán cơ bản là như thế này:

// s[i] = a[1] + a[2] + ... + a[i]
for (i: 1 -> n)
    ans += (số lượng các số s[j] có j >= i và s[j] = s[i-1] + k)

[rogp10]

O(n^2) thì chỉ cần rolling sum thôi hash gì đâu.

O(nlogn): gợi ý là bạn sẽ cần (subsum => count).

[Red_Sand (mondlicht1)]

Muốn truy cập vị trí lưu số mảng sum to k thì hm[k] thôi nha, k cần duyệt từ begin đến end đâu. Hash map nó tuyệt vời ở chỗ đó.

[Duc_Khai_Tong (da sun kid)]

cách này cũng thế :((

[Duc_Khai_Tong (da sun kid)]

Em chưa hiểu cách này, với cả bài tập phần ánh xạ từ điển nên e muốn dùng hm

[noname00 (HK boy)]

Thì mình có nói là bạn dùng tổng tiền tố + map mà. hm của bạn có chạy đi đâu đâu

[hungaya (Hung)]

Bạn duyệt từ vị trí 0 đến n-1, với n là chiều dài của mảng. Tại lần duyệt thứ i có các biến sau:

• sum có kiểu int : sum = sum + a[i], khởi tạo sum = 0. sum là tổng tiền tố.
• count có kiểu int : đếm dãy con có tổng bằng k, khởi tạo 0 luôn.
• numSums kiểu map<int, int> : dãy con từ a[0] đến a[j] (0 < j < i) có tổng bằng “key” xuất hiện “value” lần, khởi tạo không có key-value pair nào, khi key được tạo thì value = 0.

Bật mí nhiêu đây thôi
Độ phức tạp O(n) nhé

[Duc_Khai_Tong (da sun kid)]

Mình thấy như thế dãy con chỉ là từ a[0] đến a[i] có phải k

[rogp10]

Bạn thử suy nghĩ theo hướng prefix sum sẽ thấy là duyệt đủ hết, không thiếu

[hungaya (Hung)]

Phần còn lại là bạn tính count như thế nào từ sum và numSums. Có 2 trường hợp count thay đổi:

• Dãy con từ a[0] tới a[i] có tổng bằng k, khi đó count tăng lên 1
• Dãy con từ a[pi] tới a[i] (0 < pi < i) có tổng bằng k, mà dãy con từ a[0] đến a[i] có tổng bằng sum, nên dãy con từ a[0] tới a[pi-1] có tổng bằng sum - k. Với mỗi giá trị pi, count tăng lên 1. Với n giá trị pi, count tăng lên n, hay count tăng numSums[sum-k].

Minh hoạ cho trường hợp 2 rõ hơn:

• (a[0] + a[1] + … + a[pi-1]) + (a[pi] + … + a[i]) = sum
• (a[0] + a[1] + … + a[pi-1]) + k = sum
• a[0] + a[1] + … + a[pi-1] = sum - k

---

PHP

function subarray_count($total, $numbers)
{
    $count = 0;
    $sum = 0;
    $numSums = [];

    foreach ($numbers as $num) {
        $sum += $num;

        if ($sum == $total) {
            $count++;
        }

        if (array_key_exists($sum - $total, $numSums)) {
            $count += $numSums[$sum - $total];
        }

        if (array_key_exists($sum, $numSums)) {
            $numSums[$sum]++;
        } else {
            $numSums[$sum] = 1;
        }
    }

    return $count;
}

[do_tong]

#include <bits/stdc++.h>
using namespace std;
long long n,a[1000000],maxn=0,k,dau,cuoi;
long long  tong(int x,int y)
{long long t=0;
    for(int i=x;i<=y;i++)
        t=t+a[i];
return t;
}
int main()
{cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
   if(tong(i,j)%k==0&&j-i+1>maxn)  {maxn=j-i+1;dau=i;cuoi=j;}
    cout <<maxn<< " " <<endl ;
    for(int i=dau;i<=cuoi;i++)
        cout<<a[i]<<" ";
    return 0;
}

dãy con dài nhất có tổng chia hết cho k
Mọi người xem code này đc ko ,mong mọi người góp ý