image.png
采用 HashMap 记录减少时间复杂度:
/// https://leetcode.cn/problems/two-sum
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
use std::collections::HashMap;
use std::option::Option;
let mut map = HashMap::with_capacity(nums.len());
for index in 0..nums.len(){
if let Some(k) = map.get(&(target - nums[index])){
if *k != index {
return vec![*k as i32,index as i32];
}
}else {
map.insert(nums[index], index);
}
}
panic!("not found");
}
#[cfg(test)]
mod tests {
#[test]
fn two_sum_test() {
use super::two_sum;
let nums = vec![2,11,7,15];
let target = 9;
let result = two_sum(nums,target);
assert_eq!(result, vec![0,2]);
}
}
复杂度分析
空间复杂度: O(N)：主要是记录 hash 值。
时间复杂度: O(N)：单次查找 O(1)， 最多遍历 N 次。
