我要招人

去企业版

首页 > 试题广场 >

整数对查找

[编程题]整数对查找

热度指数：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)

Python

卡尔荣咯吱盒

这个似乎可以？

Python

class FindPair:
def countPairs(self, A, n, tsum):
# write code here
cnt=0
for i in range(len(A)):
cnt = cnt+A[i+1:].count(tsum-A[i])
return cnt

发表于 2021-03-23 11:07:33 回复(0)

Python

frank_123

class FindPair:
    def countPairs(self, A, n, tsum):
        # write code here
        d = {}
        res = 0
        nres = 0
        for i in A:
            if i not in d:
                d[i] = 1
            else:
                d[i] += 1
        for k, v in d.items():
            if k != (tsum - k) and (tsum - k) in d:
                res += d[k] * d[tsum - k]
        if tsum % 2 == 0 and (tsum / 2) in d:
            nres = d[tsum / 2] * (d[tsum / 2] - 1) / 2
        return res / 2 + nres

发表于 2019-08-22 18:26:41 回复(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)

Python

questRush

# -*- coding:utf-8 -*-
class FindPair:
    def countPairs(self, A, n, tsum):
        # write code here
        from collections import Counter
        if A == []:
            return 0
        a, b, cnt = Counter(A), list(set(A)), 0
        while len(b) != 0 :
            i = b[0]
            j = tsum - i
            if j in a and j != i:
                cnt += a[i] * a[j]
                del a[i], a[j]
                del b[b.index(i)]
                del b[b.index(j)]
            elif not j in a:
                del a[i]
                del b[b.index(i)]
            elif i == j:
                cnt += (a[i] * (a[i] - 1)) // 2
                del a[i]
                del b[b.index(i)]
        return cnt

编辑于 2017-04-02 18:50:44 回复(0)

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)