"Three sums" 问题 space 复杂性 - 为什么是 O(n)？

Question

Leetcode - 三个和

def threeNumberSum(array, targetSum):
    array = sorted(array)
    results = []
    for idx, elem in enumerate(array):
        i = idx + 1
        j = len(array) - 1
        target = targetSum - elem
        while i < j:
            currentSum = array[i] + array[j]
            if currentSum == target:
                result = [array[i], array[j], array[idx]]
                results.append(sorted(result))
                i += 1 
                j -= 1 
            elif currentSum < target:
                i += 1
            else:
                j -= 1

    return results

所以时间是 O(n^2)，我没问题，但是根据 Algoexpert.io，space 是 O(n)，我不确定为什么。他的解释是：

"We might end up storing every single number in our array, if every single number is used in some triplet, we will store a lot of numbers and it is going to be bound by O(n) space. Even if some numbers are used multiple times, it will be bounded by O(n)"

但我还不能理解他的解释。如果提供的数组具有（几乎）所有独特的三元组排列总和为该目标数，那么 space 复杂度不是 n choose 3 吗？如果它的 n 选择 k=3 简化它将产生 O(n^3).

但是请注意，Algoexpert 问题对输入数组有一个额外的假设，即每个元素都是不同的，而 Leetcode 版本没有这个假设。我将如何在 space 复杂性分析中正式处理该信息？

Answer 1

如果您的代码是正确的（我没有理由认为它不是），那么匹配三元组列表的 space 复杂度实际上是 O(n²).

不是O(n³)因为任何三元组的第三个成员由前两个唯一确定，所以这个值没有选择的自由。

如果所有的数都是唯一的，那么space的要求肯定是O(n²):

>>> [len(threeNumberSum(range(-i,i+1),0)) for i in range(1,10)]
[1, 2, 5, 8, 13, 18, 25, 32, 41]

你应该能够确信这个系列中的术语对应于ceil(n²/2)。（参见 https://oeis.org/A000982）。

如果列表中有重复的数字，那么由于 的要求，整体 space 要求应该减少（相对于 n）返回数组中的唯一 三元组。

"Three sums" 问题 space 复杂性 - 为什么是 O(n)？

"Three sums" problem space complexity - Why is it O(n)?

python

algorithm

complexity-theory

space-complexity