C++ 实现：计算给定序列中元素互不相同的三元组数量

要解决这个问题，我们可以使用组合数学的方法来计算满足条件的三元组数量。具体步骤如下： 1. 首先计算所有可能的三元组的总数。 2. 然后减去那些不满足条件的三元组（即存在至少两个元素相同的情况）。 代码实现 ```cpp #include <iostream> #include <vector> #include <unordered_map> using namespace std; long long countValidTriplets(const vector<int>& A) { int n = A.size(); unordered_map<int, int> freq; // 统计每个元素的频率 for (int num : A) { freq[num]++; } // 计算所有可能的三元组总数 long long total = (long long)n * (n - 1) * (n - 2) / 6; // 计算不满足条件的三元组数量 long long invalid = 0; for (auto& pair : freq) { int count = pair.second; if (count >= 2) { invalid += (long long)count * (count - 1) / 2 * (n - count); } if (count >= 3) { invalid += (long long)count * (count - 1) * (count - 2) / 6; } } // 返回满足条件的三元组数量 return total - invalid; } int main() { vector<int> A = {1, 2, 2, 3, 4}; cout << "Number of valid triplets: " << countValidTriplets(A) << endl; return 0; } ``` 代码解释 1. 统计频率：我们使用一个 `unordered_map` 来统计每个元素在序列中出现的次数。 2. 计算总数：所有可能的三元组总数为 `C(n, 3)`，即 `n * (n - 1) * (n - 2) / 6`。 3. 计算无效三元组： - 对于每个元素，如果它出现了至少两次，那么包含它的三元组中至少有两个元素相同。 - 如果元素出现了至少三次，那么包含它的三元组中所有三个元素都相同。 4. 返回结果：满足条件的三元组数量为总数减去无效三元组的数量。 额外需要注意的逻辑点 - 确保 `n` 大于等于 3，否则没有有效的三元组。 - 注意 `long long` 类型的使用，避免整数溢出。 - 在处理频率时，确保 `unordered_map` 的键类型与序列元素类型一致。 ######[AI写代码神器 | 561点数解答 | 2025-02-10 16:51:50]