我要招人

去企业版

首页 > 试题广场 >

整数对查找

[编程题]整数对查找

热度指数：10513 时间限制：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)

Java

Jlu小童

import java.util.*;

public class FindPair {
    public int countPairs(int[] A, int n, int sum) {
        // write code here
        Map<Integer, Integer> map=new HashMap<Integer, Integer>();
        Arrays.sort(A);
        int count=0;
        for(int i=0; i<n; i++){
            count+=map.getOrDefault(sum-A[i], 0);
            map.put(A[i], map.getOrDefault(A[i], 0)+1);
        }
        return count;
    }
}

发表于 2022-01-05 16:50:37 回复(0)

Java

SnailLLL

import java.util.*;

public class FindPair {
    public int countPairs(int[] A, int n, int sum) {
        // write code here
        HashMap<Integer,Integer> map=new HashMap<>();
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<n;i++){
            map.put(A[i],map.getOrDefault(A[i],0)+1);
            set.add(A[i]);
        }
        int count=0;
        Iterator<Integer> iterator=set.iterator();
        while(iterator.hasNext()){
            int key=iterator.next();
            int num1=map.getOrDefault(key,0);
            int num2=map.getOrDefault(sum-key,0);
            if(num1>0 && num2>0) count+=(key==sum-key)?
                (num1/2>0?(num1-1)*num1/2:0):num1*num2;
            if(num1!=0) map.remove(key);
            if(num2!=0) map.remove(sum-key);
        }
        return count;
    }
}

发表于 2021-10-18 12:24:56 回复(0)

Java

圣诞节的安徒生

没有排序，就类似于冒泡排序一样进行了一次冒泡，遍历数组后得到了配对成功的计数值

编辑于 2018-09-09 19:02:31 回复(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)

Java

010101010101

import java.util.*;

public class FindPair {
public int countPairs(int[] A, int n, int sum) {
// write code here
int num=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(i==j)
{
continue;
}
else if(A[i]+A[j]==sum)
{
num++;
}
}
}
return num/2;
}
}

发表于 2017-11-14 16:03:49 回复(0)

Java

Holiday_12138

import java.util.*;

public class FindPair {
    public int countPairs(int[] A, int n, int sum) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        int res=0;
        for(int i=0;i<n;i++){
            if(map.containsKey(sum-A[i]))
                res+=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 res;
    }
}

发表于 2017-05-02 19:59:07 回复(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)

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)

Java