整数对查找

[编程题]整数对查找

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