javascript - 以下算法的 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²).