HashMap

建立一個鍵(key)對應值(value)的表，存的位置用hash(key)%容器(bucket)數量決定，當我們把nums轉成hashmap，key為出現數字，value為出現次數，這邊省略hash，可以得到圖1，要找值時就能透過%5找到該值是否存在與出現次數，因此時間複雜度O(1)。

圖1

碰撞

理想是不要發生碰撞，但只要資料夠多或是存的bucket太少，就會發生多筆資料搶一個bucket，如圖2發生碰撞可以用linklist或向量Vec<T>來解決。

圖2

HashSet

跟HashMap做法一樣但不存值，主要是判斷值是否出現過。

來源：https://doc.rust-lang.org/std/collections/struct.HashSet.html

使用HashMap來解1679. Max Number of K-Sum Pairs

輸入：nums = [1,2,3,4], k = 5

輸出：2

限制：

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^9

• 1 <= k <= 10^9

做法1：先對向量陣列建立hashmap，key是出現數字，value是出現次數，再依序去找是否有成對總和等於k，需注意如果num=k-num，出現次數2次以上。

use std::collections::HashMap;

impl Solution {
    pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
        //create HashMap keys are number and values are count of the num
        let mut hashmap = HashMap::new();
        let mut pairs = 0;
        for &num in nums.iter() {
            hashmap.entry(num).and_modify(|count| *count+=1).or_insert(1);
        }
        //loop nums if k-num is in the hashmap key of num and k-num of count plus 1,output add 1;
        for &num in nums.iter() {
            let pair_value = k-num;
            if (hashmap.get(&num).unwrap_or(&0)>&0 && hashmap.get(&pair_value).unwrap_or(&0)>&0) {
                if(pair_value==num){
                    if (hashmap.get(&num).unwrap_or(&0)>&1){
                        hashmap.entry(num).and_modify(|count| *count-=2);
                    pairs+=1;
                    }
                } else {
                    hashmap.entry(num).and_modify(|count| *count-=1);
                    hashmap.entry(pair_value).and_modify(|count| *count-=1);
                    pairs+=1;
                }

            }
        }
        return pairs
    }
}

時間複雜度：O(n)

建立HashMap時會使用&num主要是借用檢查規則，如果不借用nums中的值會被移動到num，跑第二次回圈時值就失效了。

第二個找pair_value時不需要借用是因為我們判斷完後就不需要再去拿值了可以把所有權交出去。

for &num in nums.iter() {
            hashmap.entry(num).and_modify(|count| *count+=1).or_insert(1);
        }

做法2：一邊對向量陣列建立hashmap，一邊找是否有成對和等於k的值存在，可以減少做一個迴圈O(n)的時間。

use std::collections::HashMap;

impl Solution {
    pub fn max_operations(nums: Vec<i32>, k: i32) -> i32 {
        //create HashMap keys are number and values are count of the num
        let mut hashmap = HashMap::new();
        let mut pairs = 0;
        for num in nums {
            if let Some(count) = hashmap.get_mut(&(k-num)){
                if(*count>0){
                    *count -=1; 
                    pairs+=1;
                }
                if(*count==0){
                    hashmap.remove(&(k-num));
                }
            } else {
                hashmap.entry(num).and_modify(|count| *count+=1).or_insert(1);
            }
        }
        return pairs
    }
}

時間複雜度：O(n)

Day5 總結

1. HashMap介紹
2. std::collections::HashMap函式庫使用

參考資料

1. https://doc.rust-lang.org/std/collections/struct.HashMap.html
2. https://doc.rust-lang.org/std/collections/struct.HashSet.html