描述
给定长度为 n 的正整数序列 a 1,a 2…,a n，请回答有多少对 {i,j} 满足 i<j 且 a i +a j=k
输入描述
第一行两个整数 n,k
第二行 n 个整数，表示序列中的数
输出描述
输出一个整数，表示答案
用例输入 1
4 3
1 1 2 2
用例输出 1
4
提示
样例1解释
在序列 1,1,2,2 中，a 1+a 3=3, a 1+a 4=3, a 2 +a 3 =3, a 2 +a 4=3
所以符合题意的数对有 {1,3},{1,4},{2,3},{2,4}，共 4 对
数据范围
对于 20% 的数据，2≤n≤1000,1≤k≤2000,1≤a i ≤1000，a i两两不同
对于 50% 的数据，2≤n≤100000,1≤k≤200000,1≤a i ≤100000，a i两两不同
对于 100% 的数据，2≤n≤100000,1≤k≤200000,1≤a i≤10 9 ，序列中可能有相等的数
【以下回答由 GPT 生成】
## 根据题目要求我们要找到有多少对数满足其和等于给定的值，我们可以遍历整个序列，并使用一个哈希表来记录每个数出现的次数。
## 然后，对于每个数a，我们可以计算出与之配对的数b=k-a的个数。
## 最后，将所有的配对数相加即可得到满足条件的数对的个数。
def countPairs(nums, k):
counts = {} ## 哈希表，用来记录每个数出现的次数
result = 0 ## 结果变量
for num in nums:
complement = k - num ## 计算与当前数配对的数的值
if complement in counts: ## 如果配对的数已经在哈希表中存在
result += counts[complement] ## 将配对的次数加到结果中
if num in counts: ## 如果当前数已经在哈希表中存在
counts[num] += 1 ## 将当前数的出现次数加1
else:
counts[num] = 1 ## 初始化当前数的出现次数为1
return result
## 测试示例
nums = [1, 1, 2, 2]
k = 3
countPairs(nums, k)
# 输出为 4
【相关推荐】
#include <iostream>
#include <vector>
#include <algorithm>
int countPairs(std::vector<int>& arr, int k) {
std::sort(arr.begin(), arr.end()); // 对序列进行排序
int left = 0;
int right = arr.size() - 1;
int count = 0;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == k) {
count++;
left++;
right--;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return count;
}
int main() {
int n, k;
std::cin >> n >> k;
std::vector<int> arr(n);
for (int i = 0; i < n; i++) {
std::cin >> arr[i];
}
int result = countPairs(arr, k);
std::cout << result << std::endl;
return 0;
}
上面是一个示例demo，看看对你有没有帮助的
希望可以采纳
//O(n)
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
const int N=1e5+10;
typedef long long ll;
map<ll,ll>cnt;
bool st[N];
ll b[N];
int main()
{
ll n,k;
cin>>n>>k;
for(ll i=0;i<n;i++)
{
cin>>b[i];
if(!st[b[i]])
{
cnt[b[i]]=1;
st[b[i]]=1;
}
else
cnt[b[i]]+=1;
}
ll s=0;
for(lli=0;i<n;i++)
{
ll y=k-b[i];
if(st[y])
{
s+=cnt[y];
}
cnt[b[i]]-=1;
}
cout<<s<<endl;
return 0;
}
/*
4 3
1 1 2 2
*/