三重数求和算法时间复杂度疑问：O(n²logn)还是O(n²)？

你的算法的时间复杂度是O(N²)，而非O(N²logN)，排序的时间开销在大N场景下可以忽略，原因如下：

1. 各部分时间开销拆解 #

• 排序阶段：JavaScript的Array.sort()多数实现采用Timsort算法，时间复杂度为O(NlogN)，N为数组长度。
• 嵌套循环阶段：外层for循环执行O(N)次，每次外层循环对应的内层双指针while循环最多遍历O(N)个元素（左右指针从两端向中间收缩，总移动次数不超过数组长度），因此这部分时间复杂度为O(N²)。

2. 量级对比与主导项判断 #

分析时间复杂度时只保留增长最快的主导项：

• 当N足够大时，N²的增长速度远快于NlogN（比如N=1000时，N²=10^{6，NlogN≈10}4，前者是后者的100倍；N=10^{4时，N²=10}8，NlogN≈1.4×10^5，差距进一步拉大）。
• 因此O(NlogN + N²)可简化为O(N²)，排序的O(NlogN)开销相对于O(N²)的嵌套循环，在大N场景下可以忽略不计。

代码逻辑验证 #

你的双指针思路是三数之和问题的高效解法：排序后固定第一个元素，通过左右指针收缩寻找符合条件的另外两个元素，避免了暴力三重循环O(N³)的高开销，是该问题的最优解法之一。

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