给定一个int数组A及其大小n以及需查找的和sum，请返回数组中两数之和为sum的整数对的个数。保证数组大小小于等于3000。
测试样例：
[1,2,3,4,5],5,6
返回：2
[编程题]整数对查找
//虽然很low ,但代码看起简单，哈哈
class FindPair {
public:
int countPairs(vector<int> A, int n, int sum) {
int i,j,count=0;
for( i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)continue;
if(A[i]+A[j]==sum)count++;
}
}
return count/2;
}
};
发表于 2019-07-19 12:02:18
回复(1)
class FindPair {
public:
int countPairs(vector A, int n, int sum) {
// write code here
sort(A.begin(),A.end());
int low = 0,high = n-1;
int count = 0;
while(low < high)
{
if(A[low]+A[high] < sum)
low++;
else if(A[low]+A[high] > sum)
high--;
else
{
if(A[low] == A[high])
{
count += (high-low+1)*(high-low)/2;
break;
}else{
int high_num=1,low_num=1;
while(low <high-1 && A[high]==A[high-1])
{
high_num++;
high--;
}
while(low+1<high && A[low]==A[low+1])
{
low_num++;
low++;
}
low++;
high--;
count += high_num*low_num;
}
}
}
return count;
}
};
发表于 2020-07-21 22:10:02
回复(0)
不高效，但是好处理
public int countPairs(int[] A, int n, int sum) {
// write code here
Arrays.sort(A);
int k = -1;
for(int i = n-1; i>=0; i--){
if(A[i] < sum){
k = i;
break;
}
}
if(k == -1){
return 0;
}
int count = 0;
for(int i =0 ;i< k; i++){
for(int j = i+1; j<=k ;j++){
if(A[i] + A[j] == sum){
count++;
}
}
}
return count;
}
发表于 2020-07-12 18:56:30
回复(0)
// map
// 时间复杂度O(n)
// 注意 两个数相等的情况
class FindPair {
public:
int countPairs(vector<int> A, int n, int sum) {
// write code here
map<int, int> ma;
int count = 0;
for (int i = 0; i < n; ++i) {
++ma[A[i]];
if (2 * A[i] == sum) {
if (ma[A[i]] > 0) {
count += ma[A[i]] - 1;
}
}
else {
count += ma[sum - A[i]];
}
}
return count;
}
};
运行时间：6ms
占用内存：620k
发表于 2019-07-12 15:16:13
回复(0)
class FindPair {
public:
int countPairs(vector<int> A, int n, int sum) {
map<int,int> M;
for(int i=0;i<n;i++)
M[A[i]]++;
int cnt = 0;
for(int i=0;i<n;i++){
int t = sum - A[i];
if(M[A[i]]!=0){ if(A[i]==t) cnt += M[t]*(M[t]-1)/2; else if(M.find(t)!=M.end() && M[t]!=0) cnt += M[A[i]]*M[t]; M[A[i]] = M[t] = 0; } } return cnt;
}
};
编辑于 2019-03-13 02:51:13
回复(0)
要保证数组下标i、j不相等哦
import java.util.*;
public class FindPair {
public int countPairs(int[] a, int n, int sum) {
// write code here
int count = 0;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int temp = a[i] + a[j];
if (i != j) {
if (temp == sum) {
count++;
}
}
}
}
return count;
}
}
发表于 2018-05-01 11:53:13
回复(1)
import java.util.*;
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
HashMap<Integer,Integer> map=new HashMap<>();
int count=0;
for(int temp:A){
count+=map.getOrDefault(sum-temp,0);
map.put(temp,map.getOrDefault(temp,0)+1);
}
return count;
}
}
发表于 2018-02-26 23:19:52
回复(0)
python O(n) solution
from collections import defaultdict
class FindPair:
def countPairs(self, A, n, tsum):
dd=defaultdict(int)
for i in A:dd[i]+=1
setA=list(set(A))
setA.sort()
start, end = 0, len(set(A))-1
res = 0
while start < end:
if setA[start] + setA[end] < tsum:
start += 1
elif setA[start] + setA[end] > tsum:
end -= 1
else:
res += dd[setA[start]]*dd[setA[end]]
start+=1
end-=1
if setA[start]*2==tsum:
res+=dd[setA[start]]*(dd[setA[start]]-1)//2
return res
发表于 2017-10-31 17:51:45
回复(0)
import java.util.*;
/*
思路：可以将数组排序，然后左右两边两个指针往里缩(相加之和小于sum，左进，大于sum，右缩)，直到两个指针相同为止
但是这里面有一个问题，就是还要额外计算相同数字可以组成不同的配对方式(这部分参考了大佬的写法)
还有一种用hashmap的方法其实也很好用，只是开始没有想到
haiy
*/
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
int start =0,end=n-1,count=0;
Arrays.sort(A);
while(start<end){
if(A[start]+A[end]<sum) start++;
else if(A[start]+A[end]==sum){
if(A[start]==A[end]){
int t=end -start+1;
count+=(t*(t-1)/2);
break;
}
else {
int left=start+1,right=end-1;
int countleft=1,countright=1;
while(A[left]==A[start]){
countleft++;
left++;
}
while(A[right]==A[end]){
countright++;
right--;
}
count+=(countleft*countright);
start=left;
end =right;
}
}
else end--;
}
return count;
}
}
运行时间：163ms
占用内存：13580k
发表于 2017-07-06 13:53:37
回复(0)
哈希表，O(n)
#include<unordered_map>
class FindPair {
public:
int countPairs(vector<int> A, int n, int sum)
{
unordered_map<int, int> count;
int res = 0;
for (auto& i : A) ++count[i];
if ((sum & 1) == 0 && count.find(sum >> 1) != count.end())
{
res += (count[sum >> 1] * (count[sum >> 1] - 1)) >> 1;
count.erase(sum >> 1);
}
for (auto& pr : count)
{
if (pr.first < sum - pr.first && count.find(sum - pr.first) != count.end())
res += pr.second * count[sum - pr.first];
}
return res;
}
};
发表于 2017-06-30 21:11:06
回复(0)
思路：使用HashMap，key为数组中的数字，value为数组中每个数字出现的频次。遍历一次，使用一个变量count 统计两个整数之和等于给定值的对数。对于A[i]，先判断map中是否有key为（sum-A[i]），若存在count加上档案
key为（sum-A[i]）对应的value值，然后把A[i]存储到map中。
代码：
public int countPairs(int[] A, int n, int sum) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(n);
int count = 0;
for (int i = 0; i < n; i++) {
if(map.containsKey(sum-A[i])){
count +=map.get(sum-A[i]);
}
if(map.containsKey(A[i])){
map.put(A[i], map.get(A[i])+1);
}else {
map.put(A[i], 1);
}
}
return count;
}
发表于 2017-03-28 16:33:55
回复(0)
//O(n)解法
import java.util.*;
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
// write code here
HashMap<Integer, Integer> hashMap = new HashMap<>();
int count = 0;
for (int i = 0; i < n; i++) {
count += getTimes(hashMap, sum - A[i]);
hashMap.put(A[i], getTimes(hashMap, A[i]) + 1);
}
return count;
}
private Integer getTimes(HashMap<Integer, Integer> hashMap, Integer word) {
Integer time = hashMap.get(word);
return time == null ? 0 : time;
}
}
发表于 2016-11-22 16:27:28
回复(0)
//我是yishuihan，再不努力，我就找不到工作了！只能喝西北风了;
int countPairs(vector<int> A, int n, int sum) {
// write code here
if(n<=1) return 0;
int count=0;
map<int,int> mymap;
for(int i=0;i<n;i++)
mymap[A[i]]++;
map<int,int>::iterator it;
for(it=mymap.begin();it!=mymap.end();it++)
{
map<int,int>::iterator temp=mymap.find(sum-(it->first));
//假如找到了，并且不是同一个元素,如2（有3个）和4（有5个），sum=6。那么结果应该有3*5=15对;
if(temp!=mymap.end() && temp!=it)
{
count+=(it->second)*(temp->second);
it->second=temp->second=0;
}
else if(temp!=mymap.end())//找到的是同一个元素，如3和3，sum=6.结果应该有3*（3-1）/2对;
{
count+=(it->second)*((it->second)-1)/2;
it->second=0;
}
}
return count;
}
/*暴力法，有点low,时间复杂度0（n^2）,空间复杂度0（1）
int countPairs(vector<int> A, int n, int sum) {
// write code here
if(n<=1) return 0;
int count=0;
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(A[i]+A[j]==sum)
count++;
}
}
return count;
}
*/
发表于 2016-08-19 11:12:59
回复(2)
思路：
先对数组排序，维持两个指针first, last
当A[first] + A[last] > target时， A[last]要减小，即last左移
当A[first] + A[last] < target时， A[first]要增大，即first右移
当A[first] + A[last] == target时，分两种情况
-
[1, 2, 2, 3, 3, 3, 3, 4, 4, 5] target = 6, first = 1, last
= 8 A[first] = 2, A[last] = 4.
此时2重复两次， 4重复了2次 因此对数应该加上 2 * 2 -
[3, 3, 3] first = 0, last= 2, A[first] = A[last] 此时对数应该为
x = last - first + 1 = 3
加上 sum += x * (x - 1) / 2
# -*- coding:utf-8 -*-
class FindPair:
def countPairs(self, A, n, tsum):
if n < 2:
return 0
A.sort()
count = 0
i = 0
j = n - 1
while i < j:
if A[i] + A[j] == tsum:
if A[i] == A[j]:
x = j - i + 1
count += (x*(x-1)/2)
break
else:
samei = 1
samej = 1
while i < j and A[i] == A[i + 1]:
samei += 1
i += 1
while i < j and A[j] == A[j - 1]:
samej += 1
j -= 1
count += samei * samej
i += 1
j -= 1
elif A[i] + A[j] > tsum:
j -= 1
else:
i += 1
return count
发表于 2016-08-10 11:02:22
回复(0)
//数组排序后，前后两个指针向中间夹击，若找到符合要求的两个数，需要继续向中间夹，看重复的
//数有多少，需要相乘才是正确的数量；最后如果到中间符合要求，但end和start所指的数相同，则///不是左右数目相乘，而是C(n,2)
import java.util.*;
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
int[] B = A.clone();
Arrays.sort(B);
int end = n - 1, start = 0, count = 0;
while(end > start){
int left = B[start], right = B[end];
if(left + right > sum){
end --;
continue;
}
else if(left + right < sum){
start ++;
continue;
}
else {
int countLeft = 1, countRight = 1;
if(left == right){
while(B[++start] == left)
countLeft ++;
count += (countLeft * (countLeft - 1)) >> 1;
break;
}
while(B[++start] == left)
countLeft ++;
while(B[--end] == right)
countRight ++;
count += countLeft * countRight;
}
}
return count;
}
}
发表于 2015-09-24 20:22:16
回复(1)
import java.util.*;
public class FindPair {
public int countPairs(int[] A, int n, int sum) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
int count = 0;
for (int i=0; i<n; i++)
{
count += getCount(hashMap, sum - A[i]);
hashMap.put(A[i], getCount(hashMap, A[i]) + 1);
}
return count;
}
private Integer getCount(HashMap<Integer, Integer> hashMap, Integer word){
Integer get = hashMap.get(word);
return get == null ? 0 : get;
}
}
发表于 2016-12-30 13:50:23
回复(1)
问题信息
难度：
79条回答
66收藏
24354浏览
通过挑战的用户
查看代码-
2023-03-10 09:37:07 -
2023-03-09 17:44:01 -
2023-03-09 16:45:40
-
2023-03-09 12:54:34 -
2023-03-07 23:27:05
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
class FindPair { public: int countPairs(vector<int> A, int n, int sum) { int size = A.size(); if(size == 0 || n <= 0){ return 0; }//if // 排序 sort(A.begin(),A.end()); // int count = 0; for(int i = 0,j = n - 1;i < j;){ int s = A[i] + A[j]; if(s == sum){ // 3 3 3这种情况 if(A[i] == A[j]){ int x = j-i+1; count += x*(x-1)/2; break; }//if // 2 2 3 4 4 4这种情况 else{ int k = i+1; while(k <= j && A[i] == A[k]){ ++k; }//while int k2 = j-1; while(k2 >= i && A[j] == A[k2]){ --k2; }//while count += (k-i)*(j-k2); i = k; j = k2; }//else }//if else if(s < sum){ ++i; }//else else{ --j; }//else }//for return count; } };