一起学Rust-实战leetcode（一）

第二期：一起学Rust-变量及类型

第一期：一起学Rust-环境安装

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum

这是来源于leetcode的一道题，我们使用Rust来实现。

先理清思路，首先根据题目，不使用重复元素，假设只存在一个正确答案，最简单直接的思路，就是两层循环，逐个相加判断是否等于target的值，如果相等，则返回相应的索引数字。

可以看出这个算法的时间复杂度是O(nlogn)，这个就不在这里进行实现了，现在直接考虑一下是否能够优化。

考虑上面的实现，要想优化，就只能考虑O(n)复杂度了，那么就需要去掉一层循环。

将目的抽象化就是“x + y = target”，求x和y的索引，可以看做就是求x和y，目前是通过两个数字相加再与目标比较的方法，这样就需要循环出x和y的值，那么我们反过来考虑，y = target - x 通过减法来消除一个未知变量，而这个y一定是x遍历过的值或还未遍历到的。所以需要将x遍历过的值进行保存，很容易可以想到读写时间复杂度最低的就是HashMap，不过HashMap的get方法返回值是一个之前没有提到过的枚举 Option<T>类型，这个类型有两个枚举值Some(T)和None，当get的内容不存在时会返回None，存在数据时则会将值放在Some内一起返回：Some(value)，这样就可以通过match匹配得出。

下面贴出代码：

use std::collections::HashMap;

fn main(){
    let nums = vec![2, 7, 11, 15];
    let n = two_sum(nums, 9);

    println!("{:?}", n);   //结果会获取到0，1
}
fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut res:Vec<i32> = vec![];  //定义可变向量
    let mut h: HashMap<i32, i32> = HashMap::new();  //定义可变hashmap
    for (k, n) in nums.iter().enumerate() {
        let key = target - n;  //取差值
        match h.get(&key) {    //判断差值是否存在
            Some(v) => {
                //如果差值存在，则吧结果由小到大的放入向量中，
                res.push(*v);
                res.push(k as i32);
                break;
            },
            None => {
                //差值不存在则将当前值和索引存入hashmap
                h.insert(*n, k as i32);
            }
        }
    }
    res
}

练习相关的代码：https://github.com/a74946443/learn_rust