统计数组指定和三元组数量的O(n²)算法能否进一步优化

在无额外约束的通用场景下，不存在能把时间复杂度显著降到O(n²)以下的可行解法，你当前用的排序+双指针方案已经是通用场景下的最优实现之一。

为什么通用场景没法突破O(n²)下界 #

这个问题属于经典的3SUM类问题，在只允许对元素做比较、加法运算的通用计算模型下，3SUM问题的确定性算法复杂度下界就是O(n²)，目前没有任何公开的、经过验证的算法能在任意整数/实数输入下做到亚二次时间复杂度。
很多人会想到用哈希表优化两数和的查找过程：遍历每一个元素作为三元组第一个值，再用哈希表统计剩下的元素里两数和等于目标差值的对数，这个方案的时间复杂度依然是O(n²)，而且因为哈希表存取值的常数开销更大，实际运行效率通常还不如排序+双指针的方案，额外空间开销也更高。

可以突破O(n²)的特殊约束场景 #

只有当输入数组满足特定限制时，才存在复杂度更优的解法，这些方案都不具备通用性：

• 当数组元素的取值范围极小（比如所有元素都落在[0, M]区间，且M远小于n²），可以通过FFT卷积统计元素频率的方式计算符合条件的三元组数量，时间复杂度可以降到O(n + M log M)，但如果元素是常规32/64位整数，M的取值范围过大，这个方案完全没有可行性。
• 当数组存在大量重复元素时，可以先对相同值的元素做计数合并，再在去重后的数组上跑双指针，通过组合数直接计算同值元素构成的三元组数量，这种优化属于常数/低次项优化，不会改变O(n²)的复杂度阶，但在重复值占比高的场景下能大幅提升实际运行速度。

现有方案的实用优化技巧 #

不需要改动整体思路，加几个剪枝逻辑就能明显提升运行效率：

• 固定第一个元素nums[i]后，先算最小可能的三元组和：如果nums[i] + nums[i+1] + nums[i+2] > target，后续元素只会更大，不可能再凑出符合要求的三元组，直接终止外层循环即可。
• 同样固定第一个元素后算最大可能的三元组和：如果nums[i] + nums[len(nums)-2] + nums[len(nums)-1] < target，当前i对应的所有双指针组合都不可能达到目标值，直接跳过这个i进入下一轮循环。
• 遇到和前一个值相同的元素直接跳过，避免重复计算同值元素对应的三元组，同时减少重复计数的判断成本。

内容的提问来源于stack exchange，提问作者krishna2016