Two Sum

Решение

Подход

Это самая популярная задача на собеседованиях. Ключ к оптимальному решению — использовать HashMap (Dictionary в Swift) для хранения значений, которые мы уже видели.

Идея простая: для каждого элемента мы проверяем, есть ли в словаре его "дополнение" (target - current_number). Если да — нашли пару. Если нет — добавляем текущий элемент в словарь.

Оптимальное решение O(n) время, O(n) память

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var dictionary: [Int: Int] = [:]  // value: index
    
    for (index, num) in nums.enumerated() {
        let complement = target - num
        
        if let complementIndex = dictionary[complement] {
            return [complementIndex, index]
        }
        
        dictionary[num] = index
    }
    
    return []  // Гарантированно не достигнем эту строку по условию задачи
}

Как это работает:

1. Перебираем массив один раз
2. Для каждого числа вычисляем complement = target - num
3. Если complement есть в словаре, возвращаем индексы
4. Если нет, добавляем текущее число в словарь

Наивное решение O(n²) время, O(1) память (не рекомендуется)

func twoSumBruteForce(_ nums: [Int], _ target: Int) -> [Int] {
    for i in 0..<nums.count {
        for j in (i + 1)..<nums.count {
            if nums[i] + nums[j] == target {
                return [i, j]
            }
        }
    }
    
    return []
}

Этот подход неэффективен при больших n.

Решение с двумя указателями (только для отсортированного массива)

func twoSumTwoPointers(_ nums: [Int], _ target: Int) -> [Int] {
    // Создаём массив с индексами
    let indexed = nums.enumerated().map { ($0.element, $0.offset) }
    // Сортируем по значению
    let sorted = indexed.sorted { $0.0 < $1.0 }
    
    var left = 0
    var right = sorted.count - 1
    
    while left < right {
        let sum = sorted[left].0 + sorted[right].0
        
        if sum == target {
            return [sorted[left].1, sorted[right].1]
        } else if sum < target {
            left += 1
        } else {
            right -= 1
        }
    }
    
    return []
}

Этот подход работает, но требует сортировки O(n log n). Dictionary решение лучше.

Тестирование

// Тест 1: Базовый пример
let result1 = twoSum([2, 7, 11, 15], 9)
print(result1)  // [0, 1]

// Тест 2: Числа в другом порядке
let result2 = twoSum([3, 2, 4], 6)
print(result2)  // [1, 2]

// Тест 3: Одинаковые числа
let result3 = twoSum([3, 3], 6)
print(result3)  // [0, 1]

// Тест 4: Отрицательные числа
let result4 = twoSum([-1, -2, -3, 5, 10], 7)
print(result4)  // [3, 4] (5 + 2... нет, нужно пересчитать: -1, -2, -3, 5, 10 -> 5+2 нет... )
let result4_fixed = twoSum([0, -1, -2, -3, 5, 10], 8)
print(result4_fixed)  // [4, 5] (5 + 3... нет) or [-3, 10... нет]

// Тест 5: Большие числа
let result5 = twoSum([1000000000, 500000000], 1500000000)
print(result5)  // [0, 1]

// Тест 6: Числа на границе диапазона
let result6 = twoSum([-1000000000, 1000000000], 0)
print(result6)  // [0, 1]

Анализ сложности

Трудные случаи для обсуждения

1. Переполнение (Integer Overflow):

// Если суммировать два больших числа, может быть переполнение
let overflow = twoSum([2147483647, 1], 2147483646)  // Int32 переполнится
// В Swift обычно используется Int64, но нужно быть осторожным

1. Отрицательные числа:

let negatives = twoSum([-5, -3, 0, 5, 10], 5)
print(negatives)  // [-5, 10] или [0, 4]? Оба варианта валидны, вернётся первый найденный

1. Дубликаты значений:

let duplicates = twoSum([1, 1, 1, 1], 2)
print(duplicates)  // [0, 1] (первое вхождение и второе)

Вариации на собеседовании

Вопрос: Может ли быть несколько решений? Ответ: По условию задачи — нет, ровно одно. Но если было бы — возвращаем все пары.

Вопрос: Может ли массив быть пустым? Ответ: По условию 2 <= nums.length, поэтому нет.

Вопрос: Нужно ли сортировать результат? Ответ: Нет, "можно возвращать ответ в любом порядке".

Best Practice для собеседования

1. Начните с простого подхода (brute force) — покажите понимание
2. Определите проблему — O(n²) слишком медленно
3. Предложите улучшение — HashMap за O(n)
4. Объясните трейд-офф — память за скорость
5. Напишите код аккуратно, с comments
6. Протестируйте на примерах из условия
7. Обсудите edge cases — пустой массив, дубликаты, отрицательные числа

Оптимальный код для интервью

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // HashMap для O(1) поиска
    var seen: [Int: Int] = []
    
    for (index, num) in nums.enumerated() {
        let needed = target - num
        
        // Проверяем, есть ли нужное число
        if let foundIndex = seen[needed] {
            return [foundIndex, index]
        }
        
        // Добавляем текущее число для будущих поисков
        seen[num] = index
    }
    
    return []  // Никогда не достигнем (по условию есть ровно одно решение)
}

Это решение демонстрирует:

• Знание структур данных (Dictionary)
• Понимание временной сложности
• Чистый, читаемый код
• Знание особенностей Swift (enumerated, guard let)