一起學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