0001.两数之和.md

解题关键点

• 利用 HashMap ，空间换取时间，可以达到 O(n) 的时间复杂度
• 如果使用两重循环遍历，则没有空间占用，但是时间复杂度为 O(n^2)

代码

use std::collections::HashMap;

impl Solution {
    // rust 的默认 linter 推荐函数名和变量名采用 snake_case
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        // 创建 HashMap，如果不使用 mut 将无法追加项目
        let mut map: HashMap<i32, i32> = HashMap::new();
        // Vector 的长度获取使用 .len() 方法
        // a..b 表示 创建一个 从 a 到 b 的序列
        // 0..10 会从 0 到 9 迭代 10 次，如果想要从 0 到 10 迭代 11 次，可以写成 0..=10
        for i in 0..nums.len() {
            // 使用 &expr 表示借用指针，否则会导致指针占用引发错误
            if map.contains_key(&nums[i]) {
                // 将这里有两种写法：
                // 1. [a, b].to_vec()，将迭代器转为向量
                // 2. vec![a, b]，直接声明一个向量
                return [map[&nums[i]], i as i32].to_vec();
            }
            // 使用 .insert() 方法追加项目
            map.insert(target - nums[i], i as i32);
        }
        // 返回值的类型必须和函数声明一致，所以即使这一行永远不会执行，也要返回一个空的向量
        return Vec::new();
    }
}

测试用例

assert_eq!(vec![2, 3], two_sum(vec![2, 3, 9, 11], 20));
assert_eq!(vec![1, 2], two_sum(vec![0, -1, 1, 0], 0));
assert_eq!(vec![0, 2], two_sum(vec![0, -1, 0, 1], 0));