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

在计算机程序设计中，给定一个数组和一个目标和，我们需要找到数组中两个数字的和等于该目标和的所有配对数。这个问题看起来似乎不那么容易解决，但实际上有很多种方法可以完成这个任务。在本文中，我们将介绍如何用C++语言编写程序来计算给定和的配对数。

方法1：暴力枚举

一种简单的方法是使用两个嵌套的循环来枚举数组中所有可能的配对组合，并检查它们的和是否等于目标和。例如：

int getPairCount(int arr[], int n, int sum) {
   int count = 0;
   for (int i = 0; i < n-1; i++) {
      for (int j = i+1; j < n; j++) {
         if (arr[i] + arr[j] == sum) {
            count++;
         }
      }
   }
   return count;
}

在这个例子中，我们假设数组中的数字都是正数。如果数字中包含负数，我们需要对代码进行修改以便正确处理这些情况。这种方法的时间复杂度是O(n^2)，因为它需要检查数组中的每个数字。

方法2：使用哈希表

另一种方法是使用哈希表（unordered_map）来存储数组中的数字，并查找每个数字的补数（即与目标和相差多少）是否在哈希表中存在。如果存在，则计算配对数。例如：

int getPairCount(int arr[], int n, int sum) {
   unordered_map<int, int> map;
   int count = 0;
   for (int i = 0; i < n; i++) {
      int complement = sum - arr[i];
      if (map.find(complement) != map.end()) {
         count += map[complement];
      }
      map[arr[i]]++;
   }
   return count;
}

这个方法的时间复杂度是O(n)，因为它只需要遍历数组一次。

方法3：排序后使用双指针法

另一种方法是使用双指针法来处理排序后的数组。我们首先将数组排序，然后使用两个指针（一个指向数组开始，一个指向数组结尾）扫描数组。如果指针所指向的两个数字的和大于目标和，则将右指针左移。如果和小于目标和，则将左指针右移。如果和等于目标和，则找到了一对数字配对。例如：

int getPairCount(int arr[], int n, int sum) {
   sort(arr, arr+n);
   int count = 0;
   int i = 0, j = n-1;
   while (i < j) {
      if (arr[i] + arr[j] == sum) {
         count++;
         i++;
         j--;
      }
      else if (arr[i] + arr[j] < sum) {
         i++;
      }
      else { // arr[i] + arr[j] > sum
         j--;
      }
   }
   return count;
}

这个方法的时间复杂度是O(nlogn)，因为它需要对数组进行排序。