O(n log n)复杂度下查找数组中和为0的三元素的算法求解问题

原有思路的问题说明 #

• 首先你当前的双端点固定+二分查找的思路无法覆盖所有场景，存在漏检的可能：比如输入数组为[-10, -8, -5, 4, 6, 9]，合法三元组(-10,4,6)满足和为0，但按照你的指针滑动逻辑，当左端指针从0右移后，不会再考虑包含-10的组合，直接漏掉该解。
• 关于指针调整逻辑：即使不考虑漏检问题，未找到目标值时的调整规则为：
  1. 若A[left] + A[right] < 0，说明当前两数之和偏小，需要右移左指针增大总和
  2. 若A[left] + A[right] > 0，说明当前两数之和偏大，需要左移右指针减小总和
  3. 若A[left] + A[right] == 0，任意移动一个指针即可
• 原有思路如果修改为覆盖所有场景的版本，本质时间复杂度是O(n²)级别，不符合题目的O(n log n)要求，建议使用FFT多项式卷积方案。

FFT-based 正确实现方案 #

基于题目给出的元素取值范围限制（-5000n ~ 6000n），FFT方案的时间复杂度可以达到O(n log n)，实现步骤如下：

1. 数值偏移预处理：设置偏移量offset = 5000n，将所有数组元素映射到非负整数区间[0, 11000n]，避免多项式负次幂的问题。
2. 构造频率多项式：生成长度为11000n + 1的频率数组freq，freq[x]表示原数组中值为x - offset的元素出现次数，将该数组作为多项式A的系数。
3. 多项式平方计算：用FFT计算多项式A的平方得到多项式B，B的系数B[m]表示原数组中任意两个元素（允许重复选取同一位置元素）的和为m - 2*offset的组合数。
4. 去重修正：修正B的系数，排除不符合要求的重复计数：
   • 减去所有两个元素为同一位置的情况：对每个元素a，将B[2*(a+offset)]减1
   • 所有系数除以2，消除无序对的重复计数（(a,b)和(b,a)视为同一对）
5. 结果校验：遍历原数组中的每个元素c，检查B[(-c) + 2*offset]是否大于0，同时处理边界情况：
   • 若c + a + b = 0中a、b有和c相同的元素，需要校验对应值的出现次数是否足够（比如三个0的场景需要原数组中0的出现次数≥3，两个相同值加c的场景需要对应值的出现次数≥2）
   • 只要存在符合要求的组合，直接返回True，遍历结束未找到返回False

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