Два числа с заданной суммой

Решение: Два Числа с Заданной Суммой

Эта задача на поиск двух элементов в отсортированном массиве с заданной суммой. Факт того, что массив отсортирован, позволяет использовать эффективный подход с двумя указателями.

Подход 1: Два Указателя (Оптимальный)

Используем указатели с начала и конца массива:

def two_sum(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [nums[left], nums[right]]
        elif current_sum < target:
            left += 1  # Нужно увеличить сумму
        else:
            right -= 1  # Нужно уменьшить сумму
    
    return []  # Пара не найдена

Сложность:

• Временная: O(n)
• Пространственная: O(1)

Подход 2: Хеш-таблица (Работает для неотсортированных)

Используем словарь для хранения увиденных чисел:

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = set()
    
    for num in nums:
        complement = target - num
        
        if complement in seen:
            return sorted([complement, num])
        
        seen.add(num)
    
    return []

Сложность:

• Временная: O(n)
• Пространственная: O(n)

Подход 3: Бинарный Поиск

Для каждого элемента ищем дополнение с помощью бинарного поиска:

def two_sum(nums: list[int], target: int) -> list[int]:
    for i in range(len(nums) - 1):
        complement = target - nums[i]
        # Ищем complement в nums[i+1:]
        left, right = i + 1, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == complement:
                return [nums[i], complement]
            elif nums[mid] < complement:
                left = mid + 1
            else:
                right = mid - 1
    
    return []

Сложность:

• Временная: O(n log n)
• Пространственная: O(1)

Примеры

print(two_sum([1, 2, 3, 4, 5], 9))  # → [4, 5]
print(two_sum([-2, -1, 0, 3, 5, 7], 5))  # → [0, 5] или [-2, 7]
print(two_sum([1, 2, 3], 10))  # → []
print(two_sum([-5, -3, 0, 2, 8], 0))  # → [-5, 5] или [] если нет
print(two_sum([-10, 0, 10], 0))  # → [-10, 10]

Анализ Подходов

Два указателя — лучший выбор для отсортированного массива:

• Быстро: O(n) время
• Экономно: O(1) память
• Просто: интуитивный алгоритм

Хеш-таблица — если массив не отсортирован:

• Линейное время
• Использует дополнительную память
• Работает с дубликатами

Бинарный поиск — компромисс:

• O(n log n) время
• O(1) память
• Более сложный код

Рекомендация

Для собеседования используй подход 1 (два указателя) — это стандартное решение для отсортированного массива. Объясни, почему эта техника работает: когда сумма меньше целевой, нужно двигать левый указатель вправо (числа больше), а когда больше — правый указатель влево (числа меньше).