MiddleКодОчень частоЕщё не отвечали
Two Sum: индексы двух чисел с суммой, равной цели
Дан массив и целевое число — верните индексы двух чисел, дающих в сумме цель.
Требования:
- Считайте, что ровно одна верная пара существует; верните её два индекса.
- Нельзя использовать один и тот же элемент дважды.
- Цель — O(n) время, а не перебор за O(n²).
- Верните пустой вектор, если пары нет.
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
// ваш код здесь
}Допишите реализацию.
Используйте хеш-таблицу «значение → индекс». Для каждого элемента проверяйте, есть ли target - nums[i] уже в таблице; если да — верните оба индекса. Иначе вставьте nums[i] → i. Один проход, O(n) время и O(n) память — против перебора двойным циклом за O(n²).
- ✗Возвращать сами значения вместо их индексов
- ✗Использовать один и тот же элемент дважды для пары
- ✗Соглашаться на двойной цикл за O(n²), когда ожидается O(n)
- →Как бы вы изменили решение, если массив уже отсортирован?
- →Что меняется, если допустимых пар может быть несколько или ни одной?
Оглавление
Задача
Реализуйте twoSum: верните индексы двух чисел массива, дающих в сумме target, за один проход.
Решение
#include <vector>
#include <unordered_map>
std::vector<int> twoSum(const std::vector<int>& nums, int target) {
std::unordered_map<int, int> seen; // значение -> индекс
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
auto it = seen.find(target - nums[i]);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {}; // пары нет
}Ключевые моменты
- Один проход: дополнение
target - nums[i]ищется за O(1) вunordered_map, поэтому суммарно O(n). - Вставляем
nums[i]после проверки — иначе элемент может составить пару сам с собой. - Перебор двойным циклом тоже верен, но это O(n²); хеш-таблица меняет память на скорость.
Оглавление
