A5558.子问题 题解 前言 这个题的数据还没改，原题是求有多少对数满足加起来等于 kkk。 思路 方法 1 暴力枚举不重复的每一对数，然后判断每一对数加起来是否等于 kkk。时间复杂度 O(n2)O(n^{2})O(n2)，期望得分 100pts100 pts100pts。 方法 2 第二组数不变，排序第一组数，然后枚举第二组数，在第一组数中二分查找，找能与枚举到的那个数的数量。时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)，期望得分 100pts100pts100pts。 方法 3 用一个桶，记录第一组数的每一个数与哪个数加起来等于 kkk，然后在输入第二组数的时候判断桶的这个地方被标记多少次。时间复杂度 O(n)O(n)O(n)，期望得分 100pts100pts100pts。 代码 需要注意： > 古之有数，其名为 kkk。kkk 之大，一个 int （可能）装不下。 方法 1 代码 无任何优化和改变： 方法 2 代码 使用了 STL 函数： 方法 3 代码 使用了 unordered_map 当作桶：

#include <iostream> #include <unordered_map> using namespace std; int main(){ long long n,k; cin >> n >> k; unordered_map<long long,int> m; for (int i=0;i<n;++i){ long long t; cin >> t; ++m[k-t]; } int ans=0; for (int i=0;i<n;++i){ long long t; cin >> t; ans+=m[t]; } cout<<ans<<endl; return 0; }