Đếm cặp có tổng bằng 0

Xem PDF

Tất cả bài nộp

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

Tác giả:

nvatuan

Dạng bài

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

Cho dãy số \(A\) có \(N\) số nguyên. Hãy đếm số cặp \((i,j)\) sao cho \(A_i + A_j = 0\), với \(i < j\).

Input

Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 2*10^5)\)
Dòng thứ hai chứa dãy số \(A\) gồm \(N\) số nguyên cách nhau bởi một ký tự khoảng trống. \((|A_i| \leq 10^9)\)

Output

In ra một số nguyên duy nhất, là số cặp phần tử trong dãy \(A\) mà có tổng là 0.

Scoring

Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^4\), \(|A_i| \leq 10^6\).
Subtask \(2\) (\(60\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^6\).
Subtask \(3\) (\(100\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^9\).

Example

Test 1

Input

3
-2 0 2

Output

Note

Chỉ tồn tại một cặp phần tử \((1, 3)\) tương ứng với \(A_1 + A_3 = -2 + 2 = 0\).

Test 2

Input

6
-2 -1 0 0 1 2

Output

Bình luận

summary

code khi bí idea

#include <bits/stdc++.h>
using namespace std;
int main()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0); cout.tie(0); 
     int n,x; long long cnt=0;
     cin>>n;
     map <long long,int> m;
     while (n--) 
         cin>>x,
         cnt+=m[-x],
         ++m[x];
     cout<<cnt;
     return 0;
}

5 bình luận nữa