“三和”问题空间复杂度-为什么是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），我对此表示满意，但根据Algoexpert.io，空间为O（n），我不确定为什么。他的解释是：

“我们可能最终会在数组中存储每个数字，如果每个单个数字用在某个三元组中，我们将存储很多数字，并且将由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。）>

如果列表中有重复的数字，则由于返回数组中的unique

三元组的需求，总的空间需求应减少（相对于n）。