LeetCode — обьяснение задачи two_sum на языке Rust

Добавить комментарий

Описание задачи:

Дан массив целых чисел 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![]
  • Если цикл завершился, но решение не найдено, возвращается пустой вектор (хотя в условии задачи обычно гарантируется, что решение есть).

Как это работает?

  1. Пример:
  • nums = [2, 7, 11, 15], target = 9.
  1. Шаги:
  • 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 в этом коде

  1. HashMap — эффективный поиск за O(1).
  2. into_iter() — потребляющий итератор (после него nums нельзя использовать).
  3. if let — проверка Option.
  4. Возврат вектора — vec![] создаёт вектор.

Добавить комментарий