“三和”问题空间复杂度——为什么是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(n ² )。

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

如果所有数字都是唯一的，那么空间需求肯定是 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）。

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