LeetCode Rust - 1 - 两数之和
非常经典的入门题
解一，双指针枚举
没啥好说的，所有组合尝试一次直到找到答案
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
for (i, l) in nums.iter().enumerate() {
for (j, r) in nums[(i + 1)..].iter().enumerate() {
if l + r == target { return vec![i as i32, (j + i + 1) as i32]; }
}
}
return vec![]; // 编译器不知道必定会返回，确保编译通过
}
时间：$O(n^2)$ 空间：$O(1)$
解二，哈希表
非常经典的解法，遍历每个元素，对每个元素 v
- 新建哈希表，值指向下标
value => index的结构 - 检查哈希表中是否存在
target - v的下标- 如果存在，直接返回结果
- 不存在则在表中记录当前值的下标
pub fn two_sum(mut nums: Vec<i32>, target: i32) -> Vec<i32> {
use std::collections::HashMap;
let mut map: HashMap<i32, usize> = HashMap::new();
for (i, v) in nums.iter().enumerate() {
match map.get(&(target - v)) {
None => { map.insert(*v, i); },
Some(j) => { return vec![i as i32, *j as i32]; },
}
}
return vec![];
}
时间：$O(n)$ 空间：$O(n)$
[!NOTE] 性能
看了下 LeetCode 的提交信息，
match换成if let...else性能会好一些，原因未知