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

Question

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

我想出了以下代码：

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).

我不太确定 space 的复杂性，但直觉上我猜这是一个 O(n).

请问，correct/confirm 我的 reasoning/guess 关于时间和 space 的复杂性？

Answer 1

我同意你对时间复杂度的看法。你在循环中有一个循环，你总是将内循环中的指针移动至少 1（left 或 right）。所以就像你说的那样，O(n^2 / 2) 或 O(n^2)

编辑：对于 space 复杂性，我同意 Tassle 的回答

Answer 2

是的，时间复杂度为 O(n^2)，其中 n = nums.length，您对此的解释就足够了。

space 复杂度 O(n) 也是正确的，因为 sort() 方法中使用的合并排序算法具有这种 space 复杂度。 Space 复杂性是指除了给定的问题特定变量之外，您在代码中编写的额外 elements/variables space。对于除 sort() 方法之外的代码，有两个变量 'left' 和 'right' 以及一个数组结果，因此此循环的复杂度为 space O(n+2)，并且然后在内部while循环中对应它们也有一个变量's'，那么请注意在每次迭代中有2种可能性：-

它是同一个容器（即内存位置），其内容（即变量的值）发生了变化，因此总体上它只使用了 3 个容器，将 Space 复杂度归结为 O（常量）或简单地O(1)
每次将不同的容器分配给变量的内容；但是，这将始终伴随着清除对先前容器的搁置。因此，总的来说，我们一次只有 3 个额外的容器，这将再次导致 space 复杂度为 O(1)。

现在，程序的总体 space 复杂度为 O(n)+O(n+2)+O(1)，最终解决方案为 O(n)。

希望对您有所帮助！

Answer 3

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

考虑以下示例：

[1, -1, 2, -2, ..., n-1, 1-n, n, -n]，其中 n 是偶数。

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

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

结果推导：

对于这个序列中的任何正数a，我们可以选择b = k和c = -(a+k)来得到一个三元组，其中a是绝对值最小的元素，前提是 k > a 和 a+k <= n 即 a < k <= n-a。这为 k 提供了 n-2*a 个选择（我们从不计算任何两次，因为 b 始终为正，而 c 始终为负）。

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

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

What is the Time and Space Complexity of the 3Sum problem with the following algorithm?

javascript

algorithm

computer-science

time-complexity

space-complexity