1. 两数之和

题目链接: 两数之和

相信每个刷过LeetCode的人永远也忘不了这道题（就想当年背单词书永远也忘不了书中的第一个单词abandon哈哈哈），但是这道题用Rust来写也并不是那么简单，尤其是对于Rust新手，相信看完这道题你对Rust中的一些小细节会有更深的理解。

解法一

简单粗暴，双重循环，遍历所有的二元组直到找到符合题目要求的结果。

#![allow(unused)]
fn main() {
impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in (i + 1)..nums.len() {
                if nums[i] + nums[j] == target {
                    // 注意Rust中下标索引类型为usize，因此这里我们需要将i, j转换为i32
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]
    }
}
}

解法二

我们观察解法一中第二个for循环：

#![allow(unused)]
fn main() {
for j in (i + 1)..nums.len() {
    if nums[i] + nums[j] == target {
        ...
    }
}
}

我们换种方式思考：

#![allow(unused)]
fn main() {
for j in (i + 1)..nums.len() {
    let other = target - nums[i];
    if nums[j] == other {
        ...
    }
}
}

因此我们的目标就变成了在一个数组中寻找值，这可是HashSet/HashMap的强项啊！由于这里我们还需要获取到对应值在数组中的下标索引位置，因此这里只能用HashMap了。

#![allow(unused)]
fn main() {
use std::collections::HashMap;

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

如果你是个Rust新手的话，相信你可能会存在以下几点疑惑：

• 为什么需要use std::collections::HashMap;这一行：可能是觉得HashMap用的没有那么多吧，因此Rust并没有将HashMap列入Prelude行列当中，因此当我们需要使用HashMap时，需要手动引入。
• 前面的for i in 0..nums.len()哪去了，这个for (index, value) in nums.iter().enumerate()是个什么鬼：在Rust中推荐使用迭代器，而enumerate这个迭代器适配器返回含有(下标，值)的元组。
• 为什么if let Some(&other_index) = map.get(&other)需要用到两个引用符号：简单来说，因为所有权的问题。HashMap的get方法中传入的参数是对key的引用，返回的是Option<&value>，因此我们需要用这两个引用符号。