September 7th, 2021

404

подсел на 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]
    }
}