要求
- 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
暴力穷举法
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut res = Vec::<i32>::new();
for i in 0..nums.len(){
for j in (i+1)..nums.len(){
if (target == nums[i]+nums[j]){
res.push(i as i32);
res.push(j as i32);
}
}
}
res
}
}
HashMap
use std::collections::HashMap;
impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut res = vec![];
let mut cache = HashMap::new();
for (index, item) in nums.iter().enumerate() {
let sub = target - *item;
match cache.get(item) {
Some(pre_index) => {
res.push(*pre_index);
res.push(index as i32);
return res
},
None => {
cache.insert(sub, index as i32);
},
}
}
res
}
}
| 方法 | 耗时 | 内存 |
|暴力法|36 ms|2.2 MB|
|HashMap|0ms|2.4MB|
