Две суммы

Решение

Понимание задачи

Найти индексы двух чисел в массиве, сумма которых равна целевому значению. Каждый элемент используется только один раз, индексы должны отличаться.

Два подхода

1. Хеш-таблица (оптимальный)

• Проходим по массиву один раз
• Для каждого числа проверяем: есть ли complement = target - current_num
• Сохраняем число и его индекс в словаре
• Временная сложность: O(n), Память: O(n)

2. Два указателя (для отсортированного массива)

• Левый указатель в начале, правый в конце
• Двигаем указатели в зависимости от суммы
• Временная сложность: O(n log n), Память: O(1)

Реализация

def two_sum_hash(nums: list[int], target: int) -> list[int]:
    """Найти индексы двух чисел, сумма которых равна target"""
    seen = {}  # {число: индекс}
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    
    return []  # Не найдено


def two_sum_two_pointers(nums: list[int], target: int) -> list[int]:
    """Два указателя (для отсортированного массива)"""
    nums_with_idx = [(num, i) for i, num in enumerate(nums)]
    nums_with_idx.sort()
    
    left, right = 0, len(nums_with_idx) - 1
    
    while left < right:
        current_sum = nums_with_idx[left][0] + nums_with_idx[right][0]
        if current_sum == target:
            return [nums_with_idx[left][1], nums_with_idx[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return []

Комплексные тесты

import pytest

class TestTwoSum:
    """Набор тестов для поиска двух чисел с заданной суммой"""
    
    @pytest.mark.parametrize("nums,target,expected", [
        ([2, 7, 11, 15], 9, [0, 1]),
        ([3, 2, 4], 6, [1, 2]),
        ([3, 3], 6, [0, 1]),
        ([1, 2, 3, 4, 5], 9, [3, 4]),
        ([10, 1, 2, 7, 11, 15], 9, [0, 2]),
        ([-1, -2, -3, 5, 10], 8, [3, 4]),
    ])
    def test_two_sum_hash(self, nums, target, expected):
        """Тест метода хеш-таблицы"""
        result = two_sum_hash(nums, target)
        assert nums[result[0]] + nums[result[1]] == target
    
    def test_negative_numbers(self):
        """Отрицательные числа"""
        nums = [-10, -5, 0, 5, 10]
        result = two_sum_hash(nums, 0)
        assert nums[result[0]] + nums[result[1]] == 0
    
    def test_zero_target(self):
        """Целевое значение ноль"""
        nums = [0, 0, 1, 2]
        result = two_sum_hash(nums, 0)
        assert result == [0, 1]
    
    def test_large_numbers(self):
        """Большие числа"""
        nums = [1000000, 2000000, 3000000]
        result = two_sum_hash(nums, 4000000)
        assert nums[result[0]] + nums[result[1]] == 4000000
    
    def test_no_solution(self):
        """Нет решения"""
        nums = [1, 2, 3]
        result = two_sum_hash(nums, 10)
        assert result == []
    
    def test_single_pair(self):
        """Только одна пара"""
        nums = [5, 5]
        result = two_sum_hash(nums, 10)
        assert result == [0, 1]
    
    def test_duplicate_values(self):
        """Дублирующиеся значения"""
        nums = [1, 1, 1, 1, 2]
        result = two_sum_hash(nums, 3)
        assert nums[result[0]] + nums[result[1]] == 3
    
    def test_two_sum_two_pointers(self):
        """Тест метода двух указателей"""
        nums = [2, 7, 11, 15]
        result = two_sum_two_pointers(nums, 9)
        assert nums[result[0]] + nums[result[1]] == 9

Ключевые аспекты

• Хеш-таблица: O(n) время, O(n) память — идеально для большинства случаев
• Два указателя: требует сортировки, лучше для памяти
• Граничные случаи: дубликаты, отрицательные числа, большие значения
• Ограничения: каждый элемент используется один раз, индексы разные