amarao (amarao_san) wrote,
amarao
amarao_san

подсел на leetcode

Задача: найти в массиве два числа, которые образуют указанную сумму. Числа могут быть отрицательными, дважды одно число использовать нельзя. Надо вернуть номера индексов. По задаче решение всегда существует.

challenge: сделать быстрее, чем за o(n^2).

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut num_map = HashMap::with_capacity(nums.len());
        for (pos, num) in nums.iter().enumerate(){
            num_map.insert(num, pos);
        }
        for (second_pos, second_num) in nums.iter().enumerate(){
            let expected = target - second_num;
            if let Some(first_pos) = num_map.get(&expected){
                    if *first_pos != second_pos{
                    let mut res = vec![*first_pos as i32, second_pos as i32];
                    res.sort();
                    return res;
                }
            }
        }
        vec![-1i32, -1i32]
    }
}
Tags: rust
Subscribe

  • Greg Egan - Permutation City

    Я с удивлением узнал, что это 94ый год. Степень актуальности описанного не поменялась ни на йоту, не смотря на 20+ лет. Как многие книги Эгдана, в…

  • Greg Egan - Orthogonal

    Крайне хардкорная научная фантастика. Всё впечатление от книги (трёх книг!) можно разделить на несколько частей: * футуризм. У автора отсутствует…

  • The Long Way to a Small, Angry Planet

    Я редко дропаю научную фантастику, но такое случается. В основном, если оказывается, что вместо фантастики мне пытаются втюхать другой (не…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 18 comments

  • Greg Egan - Permutation City

    Я с удивлением узнал, что это 94ый год. Степень актуальности описанного не поменялась ни на йоту, не смотря на 20+ лет. Как многие книги Эгдана, в…

  • Greg Egan - Orthogonal

    Крайне хардкорная научная фантастика. Всё впечатление от книги (трёх книг!) можно разделить на несколько частей: * футуризм. У автора отсутствует…

  • The Long Way to a Small, Angry Planet

    Я редко дропаю научную фантастику, но такое случается. В основном, если оказывается, что вместо фантастики мне пытаются втюхать другой (не…