Day 1 - leetcode in rust: 1 Two Sum

此筆記主要討論 RUST 的 reference 與 hashMap

題目要求: 給一個陣列 nums 與 一個要達成目標的整數，從 nums 找到兩個整數相加等於目標整數的，將這兩整數組成的陣列回傳。

先獻上可以過的解答

use std::collections::HashMap;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut hash: HashMap<i32, i32> = HashMap::new(); // complement, complemnt_index
        for i in 0..nums.len(){
            let complement = target - nums[i];
            if let Some(complement_index) = hash.get(&complement){
                return vec![i as i32, *complement_index];
            }
            hash.insert(nums[i], i as i32);
        }
        vec![]
    }
}

試錯時，理解的 rust 概念

1. HashMap<key, value>

HashMap 存 key 與 value，用 key 透過 hash function 能快速查詢到 value的資料結構。
HashMap 不會有 key 與 value 的 ownership，而是用 borrow 的方式做查找。

let mut map = HashMap::new();
map.get(&key); // 回傳 Option<&V>
map.insert(key, value) // 回傳 Option<V>

HashMap::new(): 創建新的 hashMap
get(&key): 傳入 key 的 reference，從 HashMap，得到 Option 類別的 value (不是 Some 就是 None)
insert(key, value): 新增 key-value pair 到 HashMap 中。
這 method 同樣回傳 Option，如果 key 不存在 hashMap 中會回傳 None，如果有 key 在 hashMap 中了，新的 value 會覆蓋舊的 value，回傳的 Option 即是舊值。

2. reference 與借用 (borrowing)

get() 參數吃&key，因此這就是為甚麼以上第7行 get() 內為甚麼要 reference 了。

另外，以上第8行，我原本寫 vec![i as i32, complement_index] 少一個 *
噴錯

Line 8: Char 39: error: mismatched types (solution.rs)
  |
8 |                 return vec![i as i32, complement_index];
  |                                       ^^^^^^^^^^^^^^^^ expected `i32`, found `&i32`
  |
help: consider dereferencing the borrow
  |
8 |                 return vec![i as i32, *complement_index];

*complement_index:
是因為 get 方法傳回一個 Option<&V>，&V 是 value 的參考，在這裡，V 是 i32，get 傳回 Option<&i32>。

在 if let Some(complement_index) 內部，complement_index 是 i32 (&i32) 的參考，因此我要使用complement_index的實際值，就需要使用*運算子取消reference。

rust book 中 stack 與 heap這章節有精彩的討論，包含 reference 與 stack
簡單例子如下:

let x = 100; // address of x is 0, value of x is 100
let y = &x; // address of y is 1, value of y is 0 (address of x)
/*
stack 模樣
|  y |
|  x |
______
*/

在這個例子中，y 是 x 的 reference，因此 y 儲的是 x 的地址，而不是 x 的值。這種 reference 的用法避免了數據的拷貝，僅僅是對原資料的引用。

3. if let 用法

if let 的寫法 是簡化 match 的寫法

如以下範例程式碼 (來自 rust book)

   let config_max = Some(3u8);
    match config_max {
        Some(max) => println!("最大值被設為 {}", max),
        _ => (),
    }

減少 match 表達式中處理 None 部分，if let 只處理有配對到的分支。

    let config_max = Some(3u8);
    if let Some(max) = config_max {
        println!("最大值被設為 {}", max);
    }

match 的效果也可以說是 if let 加 else的組合。

if let Some(value) = some_option {
    // 處理 some_option 是 Some 的情況
} else {
    // 處理 some_option 是 None 的情況
}

vec.iter().enumerate()

我習慣用 C/C++ 的寫法，也就是用索引的方式去取陣列或 vector的值。而我在看起他人解答，看到同樣是 for loop (我的第五行) 但可以可以用 iter.iter().enumerate() 的方式

for (i, num) in nums.iter().enumerate(){
    let complement = target - num;
    // ...
}

• vec 的 iter() :回傳一個 slice 的 iterator
• enumerate() : 一個 iterator 會再迭代過程中產生當前的計數(count)和元素。

看更多關於 vec 的討論

在 stackoverflow 上的 In Rust, is a vector an Iterator? 貼文說到:
vec 不是 iterator，但它有實作 trait IntoIterator, 這可以用 for loop 將 vec 轉成所需的 iterator。

pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
}

因此可以如以下直接使用 v，但所有權(ownership)也被移動到 for 迴圈中，因此在 for 迴圈之後，將無法再使用 v。

let v = vec![1, 2, 3];

for val in v {
    println!("{}", val);
}