«Три суммы» проблемного пространства сложности - Почему это 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 ) из-за требования для уникальных триплетов в возвращаемом массиве.