problem

two sum

解析

先考虑最直接的暴力方法，然后分析时间空间复杂度，进而根据算法动作，分析可能的优化或者转换。
这里我们是找某个数并返回其index，因而可以想到hashmap
rust语言注意for与一般的用法不同
for 默认usize
给出A/B/C/D/E方法，多种变化。B考虑把Option的match转换成map_or_else()，有点复杂，放弃。

答案

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let n = nums.len();
        for i in 0..n {
            for j in i+1..n {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            } 
        }
        // return vec![];
        // vec![]
        unreachable!()
    }
}
*/
// complex analysis: 
// time: action by action, O(n2), space: O(1)
// improve the last action , time vs space or essience to find index hashmap(v,index)
use std::collections::HashMap;
use std::convert::TryFrom;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
       // A
        let mut comps: HashMap<i32, i32> = HashMap::new();
        for i in 0..nums.len() {
            // match to map
            match comps.get(&nums[i]) {
                Some(&x) => return vec![x, i as i32],
                None => comps.insert(target - nums[i], i as i32)
            };
        }
      // B
      //  let mut comps: HashMap<i32, i32> = HashMap::new();
      //  for i in 0..nums.len() {

      //      let mut result = comps.get(&nums[i]).map_or_else(|| { comps.insert(target -nums[i], i as i32); vec![]}, 
      //                                      |x| vec![x, i32::try_from(i).as_ref().unwrap()]);
      //      if result.is_empty() && (i < nums.len() - 1) {
      //          continue;
      //      } else {
      //          result
      //      };                             

      //  }
      // C
       // one improve: let mut index_hashmap = HashMap::with_capacity(nums.len());
      // D
       // let mut seen = HashMap::new();// no need specify type later will
       // for (i, num) in nums.iter().enumerate() { //use tuple,enumerate return tuple iter
       //     if seen.contains_key(num) {
       //         return vec![seen[num] as i32, i as i32];
       //     } else {
       //         seen.insert(target - num, i); // can use two push 
       //     }
       // }
       // here we can also use if let Some(&k) = seen.get(&(target -num)) 
       //                                 return vec![k as i32, i as i32];
       //                        } else {
       //                            seen.insert(target - num, i);
       //                        }
       // E

//        let mut dict: HashMap<&i32, usize>  = HashMap::new();
//        let mut res: Vec<i32> = vec![0; 2];
//        for (i, item) in nums.iter().enumerate(){
//            if dict.contains_key(&(target-item)) {
//                res[0] = dict[&(target-item)] as i32;
//                res[1] = i as i32;
//                return res;
//            }
//            else {
//                dict.insert(item, i);
//            }
//        } 


        vec![]
    }
}