这个问题要求返回一个数组元素的所有唯一三元组,这些元素加起来为零(交换两个元素在三元组中的位置不算作唯一)。
我想出了以下代码:
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)。
能否请您纠正/确认我对时间和空间复杂度的推理/猜测?
最佳答案
这看起来像是在二次时间内求解 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²).
关于javascript - 以下算法的 3Sum 问题的时空复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57641003/