以下算法的 3Sum 问题的时间和空间复杂度是多少？

Question

有这个问题要求返回数组元素的所有唯一三元组，这些元素加起来为零（交换三元组中两个元素的位置不算作唯一）。

我想出了以下代码：

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    // skipping duplicates
    if (i !== 0 && nums[i] === nums[i - 1]) continue;
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const s = nums[i] + nums[left] + nums[right];
      // too small; move to the right
      if (s < 0) left++;
      // too big; move to the left
      else if (s > 0) right--;
      // bingo
      else {
        result.push([nums[i], nums[left], nums[right]]);
        //skipping duplicates
        while (left + 1 < right && nums[left] === nums[left + 1]) left++;
        while (right - 1 > left && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      }
    }
  }
  return result;
};
// expected output: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
console.log(threeSum([-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]))

我认为时间复杂度是O(n^2)。我们假设开始时有一种排序是O(n log n)并且嵌套循环大约工作(n^2)/2次，转换为O(n^2)。所以，最后，我们只剩下O(n log n + n^2)并且因为n log n的程度较小，所以它被删除了，剩下O(n^2)。

我不太确定空间复杂度，但直觉上我猜这是一个O(n)。

您能否纠正/确认我对时间和空间复杂性的推理/猜测？

Answer 1

这看起来像是在二次时间内求解 3SUM 的标准方法。但是，我不同意有关空间复杂度的其他答案，并认为它是二次的，因为可以二次地许多不同的三元组总和为 0。

考虑以下示例：

[1, -1, 2, -2, ..., n-1, 1-n, n, -n]，哪里n是偶数。

在这种特殊情况下，有n²/4 - n/2不同的三元组总和为 0（请参阅下面此结果的推导）。这是数组大小的二次方（数组是2*n元素长）。因为您存储所有这些解决方案，这意味着您需要二次方的内存量，而线性O(n)不会削减它。

因此，最坏情况的空间复杂度也是二次的（很容易证明，总和为 0 的不同三元组不能超过二次方）。

结果的推导：

对于任何正数a在这个序列中，我们可以挑选b = k并c = -(a+k)获得三重其中a的绝对值最小的元素，前提是k > a和a+k <= n即a < k <= n-a。这给了我们n-2*a选择k（我们从不计算任何两次，因为b总是积极的，c总是消极的）。

总结所有可能a的，我们总共得到： sum((n-2*a) for a in 1...n/2) = n²/4 - n/2 = ?(n²).