C++ 中最大和的配对数量

---

我们需要找到在给定整数数组中所有具有最大和的配对的数量。一个配对由两个数字组成，而和则仅仅是将它们相加的结果。

我们将看到解决此问题的多种方案，从朴素（暴力）方法开始，然后转向更优化的方案。以下是我们将在本文中介绍的方法列表：

• 使用两个循环的暴力方法
• 使用排序 的最大和配对
• 使用排序 和哈希 的最大和配对

示例

输入

arr = [3, 6, 5, 2, 1, 2, 3, 4, 1, 5]

输出

2

任何配对的最大和为 10。两个配对给出此和：(5, 5) 和 (6, 4)。因此，答案为 2。

使用两个循环的暴力方法

暴力解法是最容易理解的一种。在这里，我们尝试数组中的每个可能的配对并计算它们的和。我们跟踪遇到的最高和。一旦我们知道最大和是多少，我们再次遍历数组并检查每个配对的和是否与最大值匹配，如果匹配，我们增加配对的数量。

让我们看看在 C++ 中计算最大和配对的过程

• 初始化最大和： 我们首先将最大和设置为一个非常小的数字，例如 INT_MIN（最小的可能整数值）。这确保我们遇到的第一个配对将始终更新最大和。
• 查找最大和： 我们使用两个循环。第一个循环选择一个数字，第二个循环选择另一个数字（在第一个数字之后）。对于每个配对，我们计算和并将其与当前最大和进行比较。如果它更大，我们更新最大和。
• 计算具有最大和的配对数量： 找到最大和后，我们重置循环并再次检查每个配对的和。这次，我们计算有多少个配对给我们最大和。

代码实现

#include<bits/stdc++.h>
using namespace std;

int maxSumPairsCnt(int a[], int n) {
   int maxSum = INT_MIN;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         maxSum = max(maxSum, a[i] + a[j]);
      }
   }
   int cnt = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (a[i] + a[j] == maxSum) {
            cnt++;
         }
      }
   }
   return cnt;
}

int main() {
   int arr[] = {3, 4, 5, 2, 1, 2, 3, 4, 1, 5};
   int n = 10;
   cout << maxSumPairsCnt(arr, n) << endl;
   return 0;
}

时间复杂度

此方法的时间复杂度为 O(n²)，其中 n 是数组的大小。这是因为我们使用了两个嵌套循环来检查每个可能的数字配对。虽然此解决方案很简单，但随着数组大小的增加，它会变得缓慢。

说明

我们使用了一种暴力方法，其中检查、计算并比较了数组中的每个配对以查找最大和。一旦我们得到最大和，我们再次循环遍历数组以计算有多少个配对具有此和。虽然这很简单且友好，但由于检查所有可能的配对的双重循环，其时间复杂度为 O(n²) 。此方法适用于小型数组，但随着大小的增加会变得效率低下。

使用排序的最大和配对

我们可以通过首先对数组进行排序来改进我们的解决方案。一旦数组排序，两个最大的元素将是数组中的最后两个元素。它们的和将是最大配对和。

排序还使计算有多少个配对具有此和变得更容易，因为类似的数字将被分组在一起。

• 对数组进行排序： 排序后，数组的最后两个元素将给出最大和。
• 计算配对： 我们现在使用两个循环遍历数组来计算有多少个数字配对的和等于此值。

现在，我们了解了我们必须做什么，所以让我们通过代码来理解 -

#include<bits/stdc++.h>
using namespace std;

int maxSumPairsCnt(int a[], int n) {
   sort(a, a + n); // Sort the array
   int maxSum = a[n - 1] + a[n - 2]; // Sum of two largest elements
   int cnt = 0;

   // Count pairs with the max sum
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (a[i] + a[j] == maxSum) {
            cnt++;
         }
      }
   }
   return cnt;
}

int main() {
   int arr[] = {3, 4, 5, 2, 1, 2, 3, 4, 1, 5};
   int n = 10;
   cout << maxSumPairsCnt(arr, n) << endl;
   return 0;
}

时间复杂度

对数组进行排序的时间复杂度为 O(n log n)，而由于嵌套循环，计算配对仍然需要 O(n²)。排序加快了查找最大和的速度，但我们仍然需要两个循环来计算配对。

说明

通过对数组进行排序，我们可以使用排序列表末尾的两个最大元素快速识别最大和。但是，我们仍然需要循环遍历所有配对以计算有多少个配对的和等于此最大值。排序提高了查找最大和的速度，但并没有完全优化计数过程，导致排序的时间复杂度为 O(n log n)，计数的时间复杂度为 O(n²) 。

使用哈希映射的最大和配对

此方法使用哈希映射来计算数组中每个元素的频率。通过存储每个数字出现的次数，我们可以有效地找到具有最大和的配对，而无需使用两个循环。

• 计算每个元素的频率： 使用哈希映射跟踪每个数字出现的次数。
• 查找最大元素： 数组中的两个最大元素将给出最大和。我们在哈希映射中查找它们。
• 计算配对： 基于两个最大数字的频率，我们计算可以形成多少个配对。如果这两个数字相同，我们使用组合公式 nC2（两个的组合）。如果它们不同，我们只需将它们的频率相乘。

以下是使用哈希映射查找最大和配对数量的代码。

#include <bits/stdc++.h>
using namespace std;

int maxSumPairsCnt(int a[], int n) {
   unordered_map freq;

   // Count the frequency of each element
for (int i = 0; i < n; i++) {
   freq[a[i]]++;
}

   // Find the two largest elements
int max1 = INT_MIN, max2 = INT_MIN;
   for (auto it : freq) {
      if (it.first > max1) {
         max2 = max1;
         max1 = it.first;
      } else if (it.first > max2) {
         max2 = it.first;
   }
}

   // Calculate the maximum sum
int maxSum = max1 + max2;
int cnt = 0;

   // Count pairs
if (max1 == max2) {
   cnt = (freq[max1] * (freq[max1] - 1)) / 2; // nC2 combinations
} else {
   cnt = freq[max1] * freq[max2];
}
   return cnt;
}

int main() {
   int arr[] = {3, 4, 5, 2, 1, 2, 3, 4, 1, 5};
   int n = 10;
   cout << maxSumPairsCnt(arr, n) << endl;
   return 0;
}

时间复杂度

时间复杂度为 O(n)

这是因为我们只需要遍历数组一次来计算每个元素的频率，然后我们进行恒定次数的操作（查找两个最大元素并计算配对的数量）。因此，此方法比以前的方法快得多。

说明

此方法使用哈希映射来计算数组中每个元素的频率。然后，我们通过扫描频率映射一次来找到两个最大元素。最后，我们使用这两个元素（如果它们相同则使用相同的元素）计算可以形成多少个配对。此方法避免了双重循环并实现了 O(n) 的时间复杂度，使其成为大型数据集最快、最有效的方法。