This article has participated in the “Newcomer Creation Ceremony” activity, and started the road of digging gold creation together

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Topic describes

This is the question of the day from code source Div2 on March 28th.

Daimayuan Online Judge

Given A list of numbers and A single number C, it is required to calculate the number of all pairs of A−B=C (the same pairs of numbers in different positions count as different pairs).

Input format

There are two lines of input.

The first row, two integers N, C.

The second line, N integers, is the string of numbers to be processed.

The output format

A line that represents the number of pairs that satisfy the requirements of A−B=C.

The sample input

4, 1, 1, 1, 2, 3Copy the code

Sample output

3
Copy the code

Data range

1≤N≤2 x 10^5, 1≤C≤2 x 10^5, they ensure that the range of N entered is less than 2^30.

Problem analysis

In this case, if we take a and B and see if the difference is equal to c as they say, that would be a lot of trouble, just like enumerating a, taking everything else as b, and doing the calculation to see if the difference is equal to C, that would be n^2, so you don’t have to think about timeout. So we’re going to turn the question:

We don’t know what number in the array can and I enumerated current surfers to C, but we know that our current enumeration number – what is the number of after C, so as long as we see in the array to have this number, if so, then you can make a number by the way, if the number of X, then X number of can.

Run the array through the hash table, counting the number of occurrences of each number, then run through the array to see if the value of the current element -c has been recorded in the hash table, and if so, add the counter to the value recorded in the hash table. Finally, output the value recorded by the counter.

(You can also enumerate b and see if the value of b+c is recorded, but I prefer addition.)

AC code

#include<iostream> using namespace std; #include<vector> #include<algorithm> #include<math.h> #include<set> #include<numeric> #include<string> #include<string.h> #include<iterator> #include<map> #include<unordered_map> #include<stack> #include<list> #include<queue> #include<iomanip> #define endl '\n'; typedef long long ll; typedef pair<ll, ll>PII; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n,k,res=0; cin >> n >> k; vector<int>v(n); map<int, int>mymap; for (int i = 0; i < n; i++) { cin >> v[i]; mymap[v[i]] ++; } for (int i = 0; i < n; i++) { if (mymap[v[i] - k] ! = 0) { res+=mymap[v[i]-k]; } } cout << res << endl; return 0; }Copy the code