C++程序计算给定和的配对数

给定一个整数数组和一个数字“和”，找出数组中和为“和”的整数对的数量。

示例：

输入 : arr[] = {1, 5, 7, -1},
sum = 6
输出 : 2
配对的和为6的元素有(1, 5) 和 (7, -1)

输入 : arr[] = {1, 5, 7, -1, 5},
sum = 6
输出 : 3
配对的和为6的元素有 (1, 5), (7, -1) 和
(1, 5)

输入 : arr[] = {1, 1, 1, 1},
sum = 2
输出 : 6
有3!对和为2的元素组合。

输入 : arr[] = {10, 12, 10, 15, -1, 7, 6,
5, 4, 2, 1, 1, 1},
sum = 11
输出 : 9

预期时间复杂度为 O(n)

Naive Solution – 一种简单的解决方案是遍历每个元素，并检查数组中是否有另一个数字可以添加到该元素中以生成和。

// C++ implementation of simple method to find count of
// pairs with given sum.
#include <bits/stdc++.h>
using namespace std;
 
// Returns number of pairs in arr[0..n-1] with sum equal
// to 'sum'
int getPairsCount(int arr[], int n, int sum)
{
    int count = 0; // Initialize result
 
    // Consider all possible pairs and check their sums
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] + arr[j] == sum)
                count++;
 
    return count;
}
 
// Driver function to test the above function
int main()
{
    int arr[] = { 1, 5, 7, -1, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 6;
    cout << "Count of pairs is "
         << getPairsCount(arr, n, sum);
    return 0;
}

输出

Count of pairs is 3

时间复杂度: O(n 2 )

辅助空间: O(1)

Efficient solution –

有一个更好的解决方案，其时间复杂度为O(n)。以下是算法 –

创建一个 map 来存储数组中每个数字的频率。(只需一次遍历)
在下一次遍历中，对于每个元素，检查它是否可以与任何其他元素（不包括自己！）组合以给出所需的和。相应地增加计数器。
完成第二次遍历后，计数器中将存储所需值的两倍，因为每个对计算两次。因此，将 count 除以2并返回。

实现以上思路如下:

// C++实现简单方法以查找给定总数的配对数。
// 包含库 
#include  
using namespace std;
 
// 返回arr [0..n-1]中总和等于'sum'的对数
int getPairsCount(int arr[], int n, int sum)
{
    unordered_map m;
 
    // 将所有元素的计数存储在map m中
    for (int i = 0; i < n; i++)
        m[arr[i]]++;
 
    int twice_count = 0;
 
    // 通过每个元素迭代并增加计数（注意，每对都被计算两次）
    for (int i = 0; i < n; i++) {
        twice_count += m[sum - arr[i]];
 
        // 如果(arr [i]，arr [i])配对满足条件，
        // 然后我们需要确保计数减少一个，以使不计算(arr [i]，arr [i])配对
        if (sum - arr[i] == arr[i])
            twice_count--;
    }
 
    // 返回twice_count的一半
    return twice_count / 2;
}
 
// Driver function to test the above function
int main()
{
    int arr[] = {1，5，7，-1，5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 6;
    cout << "Count of pairs is "
         << getPairsCount(arr, n, sum);
    return 0;
}

输出