Какова пространственная сложность моего алгоритма TwoSum?

Question

def twoNumberSum(array, targetSum):
    # Write your code here.
    for i in array:
        if targetSum-i in array and  targetSum-i != i:
            return [i, targetSum-i]
    return []

Answer 1

Сложность времени равна O(n^2), которая может быть уменьшена до O(n), если вы преобразовываете массив (python список) в набор. Сложность по пространству здесь постоянная.

def twoNumberSum(array, targetSum):
    # Write your code here.
    for i in array: # O(N)
        if targetSum-i in array and  targetSum-i != I: # O(N) because of `in` operator
            return [i, targetSum-i]
    return []

Используйте Set. Временная сложность O (n) и пространственная сложность также O (n)

def twoNumberSum(array, targetSum):
    # Write your code here.
    set_arrary = set(array)
    for i in array:# O(N)
        if targetSum-i in set_arrary and  targetSum-i != i: #O(1) 
            return [i, targetSum-i]
    return []