Учитывая массив [1,2,3,4,5,6], нам нужно найти пару чисел, которые в сумме дают заданную цель — скажем, 10. Результат должен быть (4,6).

Решение 1) На первый взгляд, программу можно легко написать, используя два цикла for для каждой возможной пары. Мы продолжаем проверять, равна ли сумма двух переменных цели или нет.

def findingSum(array, value):
    for i in range(len(array) - 1):
        for j in range(i, len(array)):
            if array[i] + array[j] == value:
                return (array[i], array[j])
    return -1

Но временная сложность будет O(n²).

Решение 2) Использование метода двух указателей
Скажем, если бы массив был отсортирован, то вместо того, чтобы найти сумму, мы могли бы использовать два указателя, один слева, а другой справа от массива. Если сумма двух чисел больше цели, мы переместим левый указатель на единицу, иначе уменьшим правый указатель на единицу. Мы можем делать это до тех пор, пока левое не станет больше правого.

def findingSum(array, value):
    # sorting the list first to show the method
    array = sorted(array)
    # do a left and right addition, left starts at 0 and right at length
    # increment left at each stage if sum is greater than target 
    # decrement right at each stage if sum is lesser than that
    i, j = 0, len(array) - 1
    while i < j:
        currSum = array[i] + array[j]
        if currSum == value:
            return array[i], array[j]
        if currSum > value:
            j -= 1
        else:
            i += 1
    return -1

Но при этом мы предполагаем, что список отсортирован или сортируется за время O (nlogn) перед операцией. Это лучше, чем метод грубой силы, но его можно улучшить.

Решение 3) Использование набора

Оптимальное решение может быть достигнуто с помощью наборов. Мы перебираем элементы и для каждого элемента сохраняем разницу значения и цели в наборе. И при переборе проверяем, нашелся элемент или нет. Таким образом, мы перебираем элементы только один раз.

# O(n) solution, create a set and add the complement of each
# element and check if the complement is present in the set
# or not. When matched, return the complement and the value
def findingSum(array, value):
    complement = set()
    for val in array:
        if val not in complement:
            complement.add(value - val)
        else:
            return (value - val, val)
        
    return -1

Временная сложность O (n)