[rust] 1. Two Sum/60 questions to solve

Leet Codeのおすすめされていた60問を解いた自己学習メモです。
Leet Codeのリスト機能
https://leetcode.com/list/xo2bgr0r

おすすめされていた元記事
https://1kohei1.com/leetcode/

1. Two Sum

https://leetcode.com/problems/two-sum/description/?envType=problem-list-v2&envId=xo2bgr0r

一言まとめ

同じリストに対して2回以上ループを回すときは、HashMapに登録しておくと、2回目以降のループの際の効率が良くなる。

1.総当たり

自力実装。

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for (index_1, num_1) in nums.iter().enumerate() {
            for (index_2, num_2) in nums.iter().enumerate() {
                if index_1 == index_2 {
                    continue
                }
                if num_1 + num_2 == target {
                    return vec![index_1.try_into().unwrap(), index_2.try_into().unwrap()]
                }
            }
        }
        return vec![]
    }
}

問題点

• 計算量がO(n^2)
• forループが2重になっていて、さらにif文があるので、indexが過剰に深くなってしまっている。
• if文が2つも不要。1つに統合できる。

2.HashMapへ登録(2回ループ)

別言語での回答を見て、rustで実装。

use std::collections::HashMap;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map: HashMap<i32, i32> = HashMap::new();
        for (index, num) in nums.iter().enumerate() {
            map.insert(*num, index as i32);
        }

        for index in 0..nums.len() {
            let complement = target - nums[index];
            if (map.contains_key(&complement) && map[&complement] != index as i32){
                return vec![index as i32, map[&complement]];
            }
        }
        return vec![]
    }
}

改善点

• 計算量がO(n)
• ネストが浅くなった
• 2回目のループ中のif文が1つに統合

3.HashMapへ登録(1回ループ)

別言語での回答を見て、rustで実装。

use std::collections::HashMap;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map: HashMap<i32, i32> = HashMap::new();

        for (index, num) in nums.iter().enumerate() {
            let complement = target - num;
            if (map.contains_key(&complement)){
                return vec![map[&complement], index as i32];
            }
            map.insert(*num, index as i32);
        }

        return vec![]
    }
}

for文の中で、ifブロック内の処理とmapに登録する処理の順序が重要。
逆だとCase3でNGとなる。

改善点

• for文が1回になるので、2よりも計算が効率的
• 最短で、ループ2回で処理が終了する(2の場合は確実にn回のループが発生する)