Hỏi cách tìm dãy số liên tiếp dài nhất có tổng bằng 0 mà chỉ n log n

[longhuy_32 (Nguyễn Cát Long Huy)]

Em làm bài này ok nhưng n^2. Bài này em làm một mảng tổng dồn, sau đó

for (int i=1; i<=n; i++)
    for (int j=1; j<i; j<=n; j++)
        if (a[i]-a[j-1]==0) cập nhật res=max(res, i-j+1);

Nhưng em làm vậy là n^2 rồi. Cho em hỏi còn cách nào nhanh hơn không ạ? Em muốn là n log n ạ. Em cám ơn

[Gio (Gió)]

• cộng dồn dãy a vào một mảng s
• khi đó nếu 1 đoạn liên tiếp = 0 thì nó sẽ cho s[i]=s[j]; vì s[j]= s[i]+ sum(a[x] với x từ i->j). như vậy bài toán trở thành đếm số cặp = nhau của dãy s. Chỉ cần sort và đếm là được

[longhuy_32 (Nguyễn Cát Long Huy)]

em cám ơn anh nhiều :)))

[AI_Android]

Dùng thêm unordered_map thì chỉ còn O(n)