P1618 三连击（升级版） 题解 python

题目描述

给定长度为 $n$ 的序列 $a_1, a_2, …, a_n$，询问有多少个不同的三元组 $(i, j, k)$ 满足 $1 \leq i < j < k \leq n$ 且 $a_i + a_j + a_k = t$，其中 $t$ 为给定的整数。

解题思路

本题需要枚举三元组 $(i, j, k)$，满足条件 $1 \leq i < j < k \leq n$。由于数据量较大，需要寻找更优解。

观察题目，可以发现 $i,j,k$ 三个数的位置是固定的，所以我们可以：将数组 $a$ 排序，枚举 $i$ 的位置，在 $i+1$ 向右扫描原数组，并在每一次扩张右端点 $k$ 时二分查找左端点 $j$，满足 $a_i+a_j+a_k=t$，即可在 $O(n^2\log n)$ 的时间内解决问题。

这种算法在处理数据规模较小的情况下，表现还可以。但实际上，仍然没有达到最优化时间复杂度$O(n^2)$。因此我们需要寻找更优解。

观察题目，我们可以对原式稍作变形：$a_j+a_k=t-a_i$。于是我们可以在枚举$i$之前，预处理出所有 $a_j+a_k$ 的值，之后问题就转化为了在预处理数组中二分查找 $t-a_i$ 值出现的次数即可。

但是在统计 $a_j+a_k$ 的值时，需要注意可以建立哈希表，将其值存储到哈希表中，这样便可以快速查找 $t-a_i$ 值出现的次数。

具体实现可以参考如下代码。

代码实现