首页 > 试题广场 >

整数对查找

[编程题]整数对查找

热度指数：10479 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int数组A及其大小n以及需查找的和sum，请返回数组中两数之和为sum的整数对的个数。保证数组大小小于等于3000。

测试样例：

[1,2,3,4,5],5,6

返回：2

算法知识视频讲解

查看答案及解析

推荐

念润

思路:

可以看成剑指Offer[排序数组中和为给定值的两个数字]的扩展。

我们先从小到大排序。

最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；

当相等时，我们分两种情况:

(1)

从i开始连续相同的个数为x,从j开始连续相同的个数为y。

故这一情况两数之和为指定值的整数对 = x * y

(2)

从i开始连续相同一直到j。这一块区域的元素个数为x = j - i + 1

故这一情况两数之和为指定值的整数对 = x * （x-1）/2

代码

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;
    }
};

编辑于 2015-08-18 19:02:11 回复(4)

luohan

class FindPair {
public:
    int countPairs(vector<int> A, int n, int sum) {
        // 牛客网用不了unordered_map，蛋疼
        map<int, int> cnt;
        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            int want = sum - A[i];
            ans += cnt[want];
            cnt[A[i]] ++;
        }
        return ans;
    }
};

发表于 2016-08-27 21:34:02 回复(5)

。。。。。。20190227205038

//虽然很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)

Aurora1

class FindPair:
    def countPairs(self, A, n, tsum):
        d, cnt = {x: 0 for x in A}, 0
        for x in A:
            d[x] += 1
        for x in d:
            t = tsum - x
            if t == x:
                cnt += d[x] * (d[x] - 1)
            elif t in d:
                cnt += d[x] * d[t]  # 注意相对位置
        return cnt / 2

编辑于 2017-03-12 11:50:56 回复(0)

C/C++

J.Fan

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)

Simms

不高效，但是好处理

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)

Leomh

//map
    int countPairs(vector<int> A, int n, int sum) {
        map<int,int>mp;
        for(auto x:A)mp[x]++;
        int ans = 0;
        for(int i=1;i<=sum/2;++i){
            if(i!=sum-i)
                ans += mp[i]*mp[sum-i];
            else ans += mp[i]*(mp[i]-1)/2;
        }
        return ans;
    }

发表于 2019-09-06 22:23:50 回复(0)

cpppppp

// 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)

C/C++

nbgao

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)

Java

AllenHua

要保证数组下标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)

Java

我是大牛膜拜吧小白

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

华科平凡

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)

Cavs

哈希表，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)

Java

Viva La Vida

思路：使用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)

dyr

//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)

Python

Yannyezixin

思路：

先对数组排序，维持两个指针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)

编程小王子

解题思路：

定义二层循环，从A[i]开始i=0,i<n依次逐层查找；匹配数列对；count计数；

class FindPair {

public:

int countPairs(vector<int> A, int n, int sum) {

// write code here

int count=0;

for(int i=0;i<n;i++){

for(j=i+1;j<n;j++){

if(A[i]+A[j]==sum)

count++;

}

return count;

}

};

发表于 2016-02-23 10:42:51 回复(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)

Java

江南消夏

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)