Leetcode #1 Two Sum 解題

人權聲明

題目說明

描述
給定一個整數數組nums和一個整數target，返回nums數組中兩個數字的索引，使它們加起來為target。
條件

每個輸入都只有一個解決方案
不會兩次使用相同的數字
可以按任何順序返回答案

範例

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

基本作法

use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut values = HashMap::new();
        for (idx, &value) in nums.iter().enumerate(){
            let look = target - value;
            if let Some(&j) = values.get(&look) {
                return vec![j, idx as i32];
            }
            values.insert(value,idx as i32);
        }
        return vec![]
    }
}

[1]

進階作法

HashMap 使用SipHash1-3，較為安全但速度較慢。
rustc_hash函式庫的FxHashMap，是目前速度最快的實現，與HashMap相比快4~84%。[2]
嘗試改寫if語句，這樣可以減少變數宣告及賦值的次數。

// 上面為rustc_hash函式庫中lib.rs檔案的程式碼，需要一點改寫
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut values = FxHashMap::default();
        let mut idx = 0;
        for &value in nums.iter(){
            let look = target - value;
            if values.get(&look) == None {
                values.insert(value,idx);
            } else{
                let &j = values.get(&look).unwrap();
                return vec![j, idx];
            }
            idx = idx + 1;
        }
        return vec![]
    }
}