Как решить Two Sum?

LeetCode 1. Найти два числа, дающих в сумме target. Оптимально — hash map за один проход: O(n) время, O(n) память.

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

Альтернативы:

• Brute force — два вложенных цикла, O(n²);
• Sort + two pointers — O(n log n), O(1) extra (нужно хранить original indices);

Вариации: Two Sum II (sorted, two pointers O(n)), 3Sum (для каждого i — two sum, O(n²)), 4Sum, Two Sum в BST (BFS + hash set). Hash map — универсальный инструмент для поиска по значению за O(1).