一起学Rust-实战leetcode（一）

• 2019 年 10 月 5 日
• 筆記

第二期：一起学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