Tổng bằng 0

Tác giả:

Dạng bài

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

Bạn được cho một dãy số \(a\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm số cặp số \((i,j) \ 1 \leq i \leq j \leq n\) sao cho \(a_i + a_{i+1} + ... + a_j = 0\)

Input

Dòng đầu tiên chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - là số phần tử của mảng.
Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(a_i\) \(( \mid a_i\mid \leq 10^9)\)

Output

Số lượng cặp số \((i,j)\) thõa mãn điều kiện trên

Example

Test 1

Input

4
-3 3 -4 4

Output

Bình luận

-1

Sì poi lơ át lét

#include <bits/stdc++.h>
    using namespace std;
    #define ll long long  

    int main()
    {
        int n, cnt = 0, ans = 0; cin >> n; ll temp,t[n+1];
        t[0] = 0;
        map<ll,int> mp;
        for (int i=1; i<=n; i++) 
        {
            cin >> temp; 
            t[i]=t[i-1]+temp; 
            mp[t[i]]++;
        }
        for (auto i:mp)
        {
            if (i.first == 0) ans += (i.second*(i.second+1))/2;
            else ans += (i.second*(i.second-1))/2;
        }
        cout << ans;
    }

-1

Vudoanh908 1:37 a.m. 19 Tháng 10, 2022

for lồng à

-7

vô_nhiễm 6:43 a.m. 27 Tháng 6, 2020

Cách dùng std::map không cần sort và cho đó phức tạp O(n) vẫn tốt hơn sort phải không ạ :))))

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

2 phản hồi