问题描述

小C、小U 和小R 三个好朋友喜欢做一些数字谜题。这次他们遇到一个问题，给定一个长度为n的数组a，他们想要找出符合特定条件的三元组 (i, j, k)。具体来说，三元组要满足 0 <= i < j < k < n，并且 max(a[i], a[j], a[k]) - min(a[i], a[j], a[k]) = 1，也就是说，最大值与最小值之差必须为1。
他们决定请你帮忙编写一个程序，计算符合这个条件的三元组数量。

---

测试样例

样例1：

输入：a = [2, 2, 3, 1]
输出：2

样例2：

输入：a = [1, 3, 2, 2, 1]
输出：5

样例3：

输入：a = [1, 3, 2, 2, 1, 2]
输出：12

问题理解

我们需要找出数组 a 中所有满足以下条件的三元组 (i, j, k)：

1. 0 <= i < j < k < n
2. max(a[i], a[j], a[k]) - min(a[i], a[j], a[k]) = 1

这意味着三元组中的三个元素必须满足最大值和最小值之差为1。

数据结构选择

为了高效地解决这个问题，我们可以考虑使用哈希表（或字典）来记录每个元素的出现次数。这样可以帮助我们快速计算符合条件的三元组数量。

算法步骤

1. 统计元素频率：首先遍历数组，统计每个元素的出现次数。
2. 计算三元组数量：
   • 对于每个元素 x，检查是否存在 x+1 和 x-1 的元素。
   • 如果存在，计算以 x 为中心的三元组数量。

具体步骤

1. 统计频率：使用一个哈希表 freq 记录每个元素的出现次数。
2. 计算三元组：
   • 遍历哈希表中的每个元素 x，检查 x+1 和 x-1 是否存在。
   • 如果存在，计算以 x 为中心的三元组数量。

代码实现

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;long long solution(vector<int> a) {// 统计元素频率unordered_map<int, int> freq;for (int num : a) {freq[num]++;}long long count = 0;// 计算三元组数量for (auto& [num, f] : freq) {// 检查 num+1 是否存在if (freq.count(num + 1)) {// 计算以 num 为中心的三元组数量// 这里需要计算组合数，具体公式为 C(f, 2) * freq[num + 1]// 其中 C(f, 2) 表示从 f 个元素中选 2 个的组合数count += (long long)f * (f - 1) / 2 * freq[num + 1];}// 检查 num-1 是否存在if (freq.count(num - 1)) {// 计算以 num 为中心的三元组数量// 这里需要计算组合数，具体公式为 C(f, 2) * freq[num - 1]count += (long long)f * (f - 1) / 2 * freq[num - 1];}}return count;
}int main() {vector<int> a1 = {2, 2, 3, 1};vector<int> a2 = {1, 3, 2, 2, 1};vector<int> a3 = {1, 3, 2, 2, 1, 2};cout << (solution(a1) == 2) << endl;cout << (solution(a2) == 5) << endl;cout << (solution(a3) == 12) << endl;return 0;
}

心得体会

1. 组合数学的应用

在计算三元组数量时，我们需要计算组合数。具体来说，对于每个元素 x，我们需要计算从 x 的频率中选择两个元素的组合数 C(f, 2)，其中 f 是 x 的出现次数。这个组合数的计算公式为：

这个公式在计算三元组数量时非常有用，因为它帮助我们快速计算出以 x 为中心的三元组数量。

2. 哈希表的高效性

使用哈希表（unordered_map）来统计元素频率是一个非常高效的方法。哈希表可以在平均 O(1) 的时间内完成插入和查找操作，这使得我们能够快速地统计每个元素的出现次数，并在后续计算中快速查找相邻元素的频率。

3. 边界条件的处理

在计算三元组数量时，我们需要特别注意边界条件。例如，当 x 的频率为1时，C(f, 2) 的值为0，这意味着以 x 为中心的三元组数量为0。此外，我们还需要确保 x+1 和 x-1 在哈希表中存在，否则计算结果会出错。

4. 时间复杂度的优化

通过使用哈希表和组合数学公式，我们能够将时间复杂度优化到 O(n)，其中 n 是数组的长度。这种优化在处理大规模数据时尤为重要，因为它避免了嵌套循环带来的高时间复杂度。

5. 代码的可读性和维护性

在编写代码时，保持代码的可读性和维护性非常重要。通过使用清晰的变量命名和注释，我们可以使代码更易于理解和维护。此外，将逻辑分解为多个小步骤，也有助于提高代码的可读性。