Как найти два числа с заданной суммой быстрее, чем за O(n²)?

Перебор всех пар — O(n²). Если для каждого числа быстро узнавать, видели ли мы target - x, хватит одного прохода: хеш-таблица отвечает за O(1) в среднем. static int[] twoSum(int[] nums, int target) { Map seen = new HashMap<>(); for (int i = 0; i < nums.length; i++) { Integer j = seen.get(target - nums[i]); if (j != null) return new int[] {j, i}; seen.put(nums[i], i); } return new int[0]; } Число кладём в карту после проверки: так элемент не сложится сам с собой.

Как найти два числа с заданной суммой…: ответ для собеседования Java

Сначала ответь вслух

Скажи ответ вслух хотя бы пару минут, потом открой эталон и сравни. Эталон открыт всем и не требует входа.

Показать ответ

Эталонный ответ

Перебор всех пар — O(n²). Если для каждого числа быстро узнавать, видели ли мы target - x, хватит одного прохода: хеш-таблица отвечает за O(1) в среднем.

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[] {j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

Число кладём в карту после проверки: так элемент не сложится сам с собой.

Как у тебя получилось?

Уточняющие вопросы

Так обычно копают глубже. Раскрой строку, когда ответишь вслух.

Уточнение 1-го уровня: Что если массив уже отсортирован?
Ответ уровня Junior
Два указателя с концов: сумма меньше цели — двигаем левый, больше — правый. O(n) по времени и O(1) по памяти.
1. Уточнение 2-го уровня: А как найти все тройки с нулевой суммой?
  Ответ уровня Middle
  Отсортировать, для каждого i искать пару двумя указателями в оставшейся части и пропускать одинаковые значения. O(n²).

Типичные ошибки

Класть число в карту до проверки и находить пару из одного элемента.
Сортировать массив, когда нужны исходные индексы.

Первоисточники

Javadoc: HashMap, откроется в новой вкладке

Быстрые задания по теме

Для темы «Хеш-таблицы в задачах» быстрых заданий пока нет

Можно проверить всю зону «Алгоритмы» тестом на 10 минут.

Проверить себя за 10 минут

Эталонный ответ

static int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[] {j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

Число кладём в карту после проверки: так элемент не сложится сам с собой.

Как у тебя получилось?

Уточняющие вопросы

Так обычно копают глубже. Раскрой строку, когда ответишь вслух.

Уточнение 1-го уровня: Что если массив уже отсортирован?

Ответ уровня Junior

Два указателя с концов: сумма меньше цели — двигаем левый, больше — правый. O(n) по времени и O(1) по памяти.

Уточнение 2-го уровня: А как найти все тройки с нулевой суммой?
Ответ уровня Middle
Отсортировать, для каждого i искать пару двумя указателями в оставшейся части и пропускать одинаковые значения. O(n²).