Дан массив целых чисел nums и целевое число target, нужно вернуть индексы двух чисел таким образом, чтобы они в сумме давали значение target.
Условие: каждое входное значение может иметь только одно решение и нельзя использовать один и тот же элемент дважды из массива.
Вы можете вернуть ответ в любом порядке.
Пример 1:
Вход: nums = [2,7,11,15], target = 9
Выход: [0,1]
Пояснение: поскольку nums[0] + nums[1] == 9, мы возвращаем [0, 1].
Пример 2:
Вход: nums = [3,2,4], target = 6
Выход: [1,2]
Пример 3:
Вход: nums = [3,3], target = 6
Выход: [0,1]
Пример решения на Rust:
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut map = HashMap::new();
for (i, n) in nums.into_iter().enumerate(){
let diff = target - n;
if let Some(&j) = map.get(&diff){
return vec![i as i32, j as i32];
}else{
map.insert(n, i);
}
}
vec![]
}
}
Этот код реализует классическую задачу «Two Sum» (нахождение двух чисел в массиве, дающих в сумме заданное значение) на языке Rust. Давайте разберём его по частям.
Разбор кода:
1. Импорт HashMap
use std::collections::HashMap;
HashMapиспользуется для хранения чисел из массива и их индексов. Это позволяет быстро проверять, встречалось ли нужное число ранее.
2. Реализация метода two_sum
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
impl Solution— реализация методов для структурыSolution(нужно только для leetcode , писать у себя можно и без этого для отладки).two_sum— публичный метод, принимающий:nums: Vec<i32>— вектор (массив) чисел,target: i32— целевая сумма.- Возвращает
Vec<i32>— индексы двух чисел, дающих в суммеtarget.
3. Создание HashMap
let mut map = HashMap::new();
- Создаётся пустая хеш-таблица (
HashMap), где: - ключ — число из массива,
- значение — его индекс.
4. Итерация по массиву
for (i, n) in nums.into_iter().enumerate() {
into_iter()— превращаетnumsв итератор, потребляя его (после этогоnumsнельзя использовать снова).enumerate()— добавляет индексiк каждому элементуn.
5. Вычисление разницы (diff)
let diff = target - n;
diff— это число, которое нужно найти вHashMap, чтобыn + diff == target.
6. Проверка наличия diff в HashMap
if let Some(&j) = map.get(&diff) {
return vec![i as i32, j as i32];
}
map.get(&diff)— ищетdiffв хеш-таблице.- Если нашлось (
Some(&j)), значит, раньше уже встречалось числоdiffна позицииj. - Возвращаем индексы
[i, j](текущий и найденный).
7. Если diff не найден — сохраняем текущее число
} else {
map.insert(n, i);
}
- Если
diffне найден, добавляем текущее числоnвHashMapс его индексомi.
8. Если пара не найдена — возвращаем пустой вектор
vec![]
- Если цикл завершился, но решение не найдено, возвращается пустой вектор (хотя в условии задачи обычно гарантируется, что решение есть).
Как это работает?
- Пример:
nums = [2, 7, 11, 15],target = 9.
- Шаги:
i=0,n=2→diff=7→7нет вHashMap→ сохраняем{2: 0}.i=1,n=7→diff=2→2есть вHashMap(j=0) → возвращаем[1, 0].
Сложность алгоритма
- Время: O(n) — проход по массиву один раз, поиск в
HashMapв среднем за O(1). - Память: O(n) — в худшем случае храним все элементы.
Ключевые концепции Rust в этом коде
HashMap— эффективный поиск за O(1).into_iter()— потребляющий итератор (после негоnumsнельзя использовать).if let— проверкаOption.- Возврат вектора —
vec![]создаёт вектор.
