Two Sum - найти два числа с заданной суммой

Two Sum: нахождение двух чисел с заданной суммой

Суть задачи

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

Подходы решения

1. Наивный подход — перебор (O(n²))

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};  // нет решения
}

Сложность: O(n²) — очень медленно при больших массивах.

2. Оптимальный подход — HashMap (O(n)) ✓

Идея: Проходим массив один раз. Для каждого числа проверяем, есть ли в HashMap число, которое в сумме с текущим даст target.

public int[] twoSum(int[] nums, int target) {
    // Ключ — число, значение — его индекс
    Map<Integer, Integer> numMap = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];  // число, которое нам нужно найти
        
        // Проверяем, есть ли искомое число в HashMap
        if (numMap.containsKey(complement)) {
            return new int[]{numMap.get(complement), i};
        }
        
        // Добавляем текущее число в HashMap
        numMap.put(nums[i], i);
    }
    
    return new int[]{};  // нет решения
}

Сложность: O(n) время, O(n) память.

Пошаговый пример

nums = [2, 7, 11, 15], target = 9

Шаг 1: i=0, nums[0]=2
  complement = 9 - 2 = 7
  numMap пусто, 7 не найдено
  numMap = {2 → 0}

Шаг 2: i=1, nums[1]=7
  complement = 9 - 7 = 2
  numMap содержит 2! Индекс: 0
  ОТВЕТ: [0, 1]

Обработка отрицательных чисел

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        
        if (numMap.containsKey(complement)) {
            return new int[]{numMap.get(complement), i};
        }
        
        numMap.put(nums[i], i);
    }
    
    return new int[]{};
}

// Пример с отрицательными числами:
// nums = [-3, 4, 3, 90], target = 0
// Шаг 1: nums[0]=-3, complement=0-(-3)=3, не найдено, numMap={-3→0}
// Шаг 2: nums[1]=4, complement=0-4=-4, не найдено, numMap={-3→0, 4→1}
// Шаг 3: nums[2]=3, complement=0-3=-3, НАЙДЕНО! ответ=[0,2]

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

public class TwoSumTest {
    private TwoSum solution = new TwoSum();
    
    @Test
    public void testBasicCase() {
        int[] nums = {2, 7, 11, 15};
        int[] result = solution.twoSum(nums, 9);
        assertArrayEquals(new int[]{0, 1}, result);
    }
    
    @Test
    public void testWithNegativeNumbers() {
        int[] nums = {-3, 4, 3, 90};
        int[] result = solution.twoSum(nums, 0);
        assertArrayEquals(new int[]{0, 2}, result);
    }
    
    @Test
    public void testSecondExample() {
        int[] nums = {3, 2, 4};
        int[] result = solution.twoSum(nums, 6);
        assertArrayEquals(new int[]{1, 2}, result);
    }
    
    @Test
    public void testLargeNumbers() {
        int[] nums = {1000000, 2000000, -1999999};
        int[] result = solution.twoSum(nums, 1);
        assertArrayEquals(new int[]{0, 2}, result);
    }
}

Почему HashMap лучше сортировки

Сортировка (O(n log n)):

• Медленнее, чем HashMap
• После сортировки индексы теряются, нужна доп. работа для их восстановления
• Модифицирует исходный массив

HashMap (O(n)):

• Одна итерация по массиву
• Сохраняет индексы
• Не модифицирует исходный массив
• Работает с отрицательными числами из коробки

Сложности

Вывод

HashMap подход — это классическое решение задачи Two Sum. Оно работает за один проход по массиву, обрабатывает отрицательные числа и любые целые значения. При интервью это именно то решение, которое хотят услышать.