题目描述

给定 $n$ 个数组 $a_1, \dots, a_n$, 找出所有的严格递增三元组($1 \leq i < j < k \leq n$) , 使得$a_i = a_k = a_j + 1$ , 输出其数量。

题解

我们要找这样的三元组:(x + 1 , x , x + 1) 。对于一个特定的x，我们要算个数，就是去考虑前缀和后缀中x + 1 的个数，快速查询x + 1的个数我们只需要使用使用哈希表即可。假如个数是a和b，答案就是a * b. 所以计算顺序是从左到右枚举中间这个x，这样枚举的好处是左右两边要考虑的区域随着从左到右枚举的过程，它们就是一个连续的前缀和后缀，方便我们更新前缀哈希和后缀哈希。移动过程中前缀哈希增添一个数，后缀哈希删除一个数。

AC 代码

C++代码

#include<bits/stdc++.h>