2020/2/7

题目描述

• 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

• 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

相关标签

数组
哈希表

解题思路

利用HashMap存储原数组中的值与下标的映射，通过HashMap可以查询元素做到O(1)的时间复杂度，一遍循环的时间复杂度为O(n)；缺点是会有更高的空间复杂度O(n)。

源代码

use std::collections::HashMap;
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let len = nums.len();
        // 用于存放 <num, index> 的哈希表
        let mut m: HashMap<i32,i32> = HashMap::new();
        let mut ans = vec![];
        for i in 0..len {
            let remain = target - nums[i];
            // 通过 target - num 得到另一个 num 作为 key 值进行查找
            m.entry(nums[i]).or_insert(i as i32);
            if m.contains_key(&remain) {
                if let Some(val) = m.get(&remain) {
                    // 排除两次都取相同元素的情况
                    if i as i32 != *val {
                        ans.push(*val);
                        ans.push(i as i32);
                        break;
                    }
                }                
            } 
        }
        ans
    }
}

• 执行用时 :0 ms, 在所有 Rust 提交中击败了100.00%的用户
• 内存消耗 :2.3 MB, 在所有 Rust 提交中击败了56.36%的用户

总结

本题涉及到了一些HashMap相关的方法，如下所示：

• pub fn insert(&mut self, k: K, v: V) -> Option<V>
  插入元素，若已存在相同key值的元素，则进行更新。
• pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
  通过传入key值的引用，返回对应元素的值的Option枚举对象。
• pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool
  通过传入key值的引用，返回一个bool值用于判断该Key值是否存在对应元素。
• pub fn entry(&mut self, key: K) -> Entry<K, V>
  通过传入key值，返回一个Entry枚举类型，一般与or_insert()连用，已达到判断key值对应元素是否存在，若不存在，则直接插入；若已经存在，则不覆盖原元素。