# ***Lưu ý: Hãy tự nghĩ cách giải trước khi xem lời giải***
## **Ý TƯỞNG**:
*Đề bài yêu cầu tìm các cặp $A_i$, $B_j$ sao cho* :\
$A_i + B_j = x$
$ \iff $ $B_j = x - A_i $
## $\Rightarrow $ Từ đó ta sẽ khai thác bài toán theo hướng:
* **Sử dụng STL unordered_map để đếm số lần xuất hiện $B_j$**
* **Duyệt 1 lần qua mảng A, đặt biến $B_j = x - A_i $**
* **Tạo 1 biến lưu kết quả, nếu $ B_j $ có tồn tại trong mảng B,
hãy cộng vào `ans` với số lần xuất hiện của $B_j$ tương ứng**
## **Độ phức tạp thuật toán**
*Với cách làm trên, **độ phức tạp thời gian là** O(n)*
**CODE THAM KHẢO* :*
```
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define fre(NAME) freopen(NAME".inp","r",stdin); freopen(NAME".out","w",stdout)
#define suyvolo ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const ll INF = 4e18;
using namespace std;
int main(){
suyvolo;
ll n,x;
cin >> n >> x;
vector<ll> A(n);
vector<ll> B(n);
unordered_map<ll,ll> count_freq; // biến đếm
for(ll i = 0 ;i < n; i++) cin >> A[i];
for(ll i = 0 ;i < n; i++) {
cin >> B[i];
count_freq[B[i]]++;
}
ll ans = 0; // biến lưu kết quả
for(ll i =0 ;i< n;i++){
ll Bj = x - A[i];
ans += count_freq[Bj]; // nếu Bj xuất hiện thì thêm vào
}
cout << ans;
return 0;
}
angwangsushi
Created at
0 likes