Задача о двух суммах – это классическая алгоритмическая задача, которая предполагает нахождение в массиве двух чисел, сумма которых равна заданной целевой сумме. В этой статье мы рассмотрим несколько подходов к решению проблемы двух сумм с использованием Python. Мы предоставим примеры кода для каждого метода и обсудим их сильные и слабые стороны.

Метод 1: грубая сила
Подход грубой силы включает в себя проверку каждой пары чисел в массиве, чтобы увидеть, соответствует ли их сумма целевому значению. Хотя этот метод имеет временную сложность O(n^2), он обеспечивает простое решение проблемы.

def two_sum_brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Метод 2: два указателя
Метод двух указателей — это оптимизированный подход, который работает при сортировке входного массива. Мы используем два указателя, один из которых начинается с начала, а другой с конца, и перемещаем их друг к другу в зависимости от суммы чисел, на которые они указывают.

def two_sum_two_pointers(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

Метод 3: хеш-карта
Использование хеш-карты позволяет нам решить задачу двух сумм с линейной временной сложностью (O(n)). Мы сохраняем разницу между целью и каждым числом в массиве как ключи на карте, а их индексы — как значения. Обходя массив, мы проверяем, существует ли текущий номер на карте.

def two_sum_hash_map(nums, target):
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    return []

Метод 4: сортировка и двоичный поиск
Этот метод включает в себя сортировку массива и выполнение двоичного поиска в отсортированном массиве. Сравнивая сумму текущей пары с целевой, мы можем соответствующим образом настроить диапазон поиска.

import bisect
def two_sum_binary_search(nums, target):
    sorted_nums = sorted(nums)
    for i, num in enumerate(sorted_nums):
        complement = target - num
        j = bisect.bisect_left(sorted_nums, complement, i + 1)
        if j < len(sorted_nums) and sorted_nums[j] == complement:
            return [nums.index(num), nums.index(complement)]
    return []

В этой статье мы рассмотрели несколько методов решения проблемы двух сумм в Python. Мы обсудили метод грубой силы, метод двух указателей, метод хеш-карты, а также метод сортировки и двоичного поиска. Каждый метод имеет свои преимущества и недостатки с точки зрения временной и пространственной сложности. Понимая эти методы, вы сможете с уверенностью решать аналогичные проблемы и выбирать наиболее подходящее решение для ваших конкретных требований.