『Rust刷算法』LeetCode1-两数之和

要求

• 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

暴力穷举法

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut res = Vec::<i32>::new();
        for i in 0..nums.len(){
            for j in (i+1)..nums.len(){
                if (target == nums[i]+nums[j]){
                    res.push(i as i32);
                    res.push(j as i32);
                }                
            }
        }
        res
    }
}

HashMap

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut res = vec![];
        let mut cache = HashMap::new();

        for (index, item) in nums.iter().enumerate() {
            let sub = target - *item;

            match cache.get(item) {
                Some(pre_index) => {
                    res.push(*pre_index);
                    res.push(index as i32);
                    return res
                },
                None => {
                    cache.insert(sub, index as i32);
                },
            }
        }
        res
    }
}

| 方法 | 耗时 | 内存 |
|暴力法|36 ms|2.2 MB|
|HashMap|0ms|2.4MB|