思路：桶装计数

观察$max - min = 1$,三元组中 必定有两个元素相等 ,形如

1.$x-1,x,x$

2.$x-1,x-1,x$

那么我们可以使用一个桶(哈希表)$d$先统计每个数出现的次数。然后枚举每一个值$x$.

第一种情况的贡献: $C(d[x] , 2) * d[x-1]$

第二种情况的贡献: $C(d[x-1] , 2) * d[x]$

累加起来即可.答案是$n^3$ 级别的，记得开$long\ long$

代码

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
unordered_map<int , ll> d;
int main() {
    int n;
    cin >> n;
    ll ans = 0;
    // 读入 + 桶计数
    for (int i = 1 ; i <= n ; i++){
        int x;
        cin >> x;
        d[x]++;
    }
    // 公式参考上面
    for (auto g : d){
        int x = g.first;
        ans += (d[x] - 1) * d[x] / 2 * d[x - 1];
        ans += (d[x - 1] - 1) * d[x - 1] / 2 * d[x];
    }
    cout << ans << endl;
	return 0;
}

题目内容

在一个小镇上，有一家古董店。这家古董店主人是一个极具收藏热情的老人，他一生都在收集和珍藏各种珍奇古董。他把他的珍藏分成了许多类别，其中包括了各种古代文物、稀有的艺术品和珍贵的文献资料等。

然而，这位老人在年轻时曾有一段失恋的经历，他的爱人因意外离世，让他深受打击。他渐渐地迷上了麻将这项运动，麻将成为了他减轻痛苦的一种方式。他甚至在自己的古董店里开了一间麻将室，邀请各位朋友前来打麻将。

一天，他在整理古董时发现了一组古董，这组古董是他年轻时收藏的。他把这些古董拿到麻将室，让朋友们来观赏和欣赏。这组古董是由 $n$ 个不同的古董组成的，老人和他的朋友们都非常喜欢这些古董。

他在整理这些古董时，发现了一组数字序列 $a_0,a_1,\cdots,a_{n-1}$ ，其中每个 $a_i$ 表示古董的编号。

他想让朋友们玩一下游戏，要求朋友们找出有多少组三元组 $< i,j,k >$ 满足 $0\le i <j<k<n$ 且 $max(a_i,a_j,a_k) - min(a_i,a_j,a_k) = 1$。

这时，老人问你是否能够帮助他计算出答案。

输入描述

第一行输入一个正整数 $n$ 。

第二行输入$n$个正整数$a_{i}$ 。

$3 \leq n \leq 200000$

$1 \leq a \leq 10^9$

输出描述

一个整数，代表合法的三元组数量。

样例$1$

输入

5
3 2 1 2 3

输出

5

样例$2$

输入

5
1 2 3 4 5

输出

0