python - "Three sums"问题空间复杂度 - 为什么是 O(n)？

Question

Leetcode - 三和

https://leetcode.com/problems/3sum/

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)，我可以接受，但是空间是 O(n)，根据 Algoexpert.io，我不确定为什么。他的解释是:

“我们可能最终将每个数字都存储在我们的数组中，如果每个数字都用于某个三元组中，我们将存储很多数字，并且它将受到 O(n) 空间的约束。即使使用了一些数字多次，它将以 O(n) 为界"

但我还无法理解他的解释。如果提供的数组具有(几乎)所有唯一的三元组排列总和到该目标数，那么空间复杂度不是 n 选择 3 吗？如果它的 n 选择 k=3 简化，它将产生 O(n^3)。

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

Answer 1

如果你的代码是正确的(我没有理由假设它不是)，那么匹配三元组列表的空间复杂度实际上是 O(n2)。

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

如果所有数字都是唯一的，那么空间需求肯定是 O(n2):

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

您应该能够满足自己，该系列中的项对应于 ceil(n2/2)。 (见 https://oeis.org/A000982)。

如果列表中有重复的数字，则由于返回数组中需要唯一的三元组，因此总体空间需求应该减少(相对于 n)。