Two Sum (Сумма двух чисел): Разбор задачи для начинающих

Почему эту задачу часто дают на собеседованиях?

Задача Two Sum — это не просто тест на знание алгоритмов. Она показывает, как вы:

• Анализируете проблему
• Улучшаете свое решение
• Думаете об оптимизации
• Работаете с базовыми структурами данных

Давайте разберем задачу по шагам

Что нужно сделать?

Представьте, что у вас есть массив чисел и какое-то целевое число. Вам нужно найти два числа из массива, которые в сумме дают целевое число.

Например:

const numbers = [3, 4, 5, 6];
const target = 7;

// Нужно найти 3 и 4, потому что 3 + 4 = 7

Решение 1: Самое простое (но не самое эффективное)

Давайте подумаем, как бы мы решили эту задачу в реальной жизни:

1. Берем первое число
2. Перебираем все остальные числа, пытаясь найти пару
3. Если не нашли, берем второе число и так далее

function findTwoNumbersSimple(numbers, target) {
    for (let i = 0; i < numbers.length; i++) {
        for (let j = i + 1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] === target) {
                return [i, j];
            }
        }
    }
    return [];  // если ничего не нашли
}

Это работает! Но медленно на больших массивах.

Решение 2: Умное решение (то, что обычно хотят увидеть)

Давайте подумаем хитрее:

• Если у нас есть число X, и мы ищем сумму равную 7
• То нам нужно найти число Y = 7 - X
• Можно запоминать уже просмотренные числа!

function findTwoNumbersSmart(numbers, target) {
    // Объект для хранения просмотренных чисел
    const seen = {};

    for (let i = 0; i < numbers.length; i++) {
        const currentNumber = numbers[i];
        // Какое число нам нужно найти?
        const needed = target - currentNumber;

        // Если мы уже видели это число раньше
        if (needed in seen) {
            return [seen[needed], i];
        }

        // Запоминаем текущее число
        seen[currentNumber] = i;
    }

    return [];
}

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Почему второе решение лучше?

1. 🚀 Скорость:

   • Первое решение: проверяет все пары (O(n²))
   • Второе решение: проходит по массиву только один раз (O(n))

2. 📝 Память:

   • Первое решение: не требует дополнительной памяти (O(1))
   • Второе решение: использует объект для хранения чисел (O(n))

Советы для собеседования

1. Начните с простого решения

   • Покажите, что вы можете решить задачу хотя бы просто
   • Объясните, почему это решение не оптимально

2. Предложите улучшения

   • Расскажите, как можно сделать лучше
   • Объясните, почему новое решение эффективнее

3. Обсудите компромиссы

   • Скорость vs Память
   • Простота vs Эффективность

Дополнительные вопросы для размышления

1. Что если в массиве могут быть отрицательные числа?

// Решение работает с отрицательными числами
const numbers = [-2, 1, -5, 4];
const target = -7;
console.log(findTwoNumbersSmart(numbers, target)); // [-5, -2]

1. Что если нужно найти не два, а три числа?

function findThreeNumbers(numbers, target) {
    numbers.sort((a, b) => a - b);
    
    for (let i = 0; i < numbers.length - 2; i++) {
        let left = i + 1;
        let right = numbers.length - 1;
        
        while (left < right) {
            const sum = numbers[i] + numbers[left] + numbers[right];
            if (sum === target) {
                return [i, left, right];
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return [];
}

1. Что если может быть несколько правильных ответов?

function findAllPairs(numbers, target) {
    const results = [];
    const seen = {};
    
    for (let i = 0; i < numbers.length; i++) {
        const needed = target - numbers[i];
        if (needed in seen) {
            results.push([seen[needed], i]);
        }
        seen[numbers[i]] = i;
    }
    
    return results;
}

Заключение

Two Sum — отличный пример того, как простая на первый взгляд задача может научить важным концепциям программирования:

• Оптимизации алгоритмов
• Использованию хеш-таблиц (объектов в JavaScript)
• Компромиссам между временем и памятью

Главное — не просто запомнить решение, а понять принцип оптимизации и почему мы используем определенные подходы.