存在重复元素
- 这道题比较简单 主要考察数据结构的使用 存在重复元素
impl Solution {
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
let set: HashSet<i32>=HashSet::from_iter(nums.clone());
set.len() != nums.len()
}
}- 我们使用hashset 来存储 然后比较长度即可 这是因为hashset的特性 不会存储重复的元素
- 所以我们只需要比较长度即可 时间复杂度为O(n) 空间复杂度为O(n)
- 当然我们也可以使用hashmap来存储 然后比较值即可 时间复杂度为O(n) 空间复杂度为O(n)
impl Solution {
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
let map: HashMap<&i32, i32> = HashMap::from_iter(nums.iter().map(|x| (x, 0)));
map.len() != nums.len()
}
}- 当然博主既然提了这道题，那肯定不会这么简单
- 开始加码 存在重复元素2
- 加码之后也很简单 我们只需要把对应的可能性丢进map里,之后每一次计算都查询一次即可。
use std::collections:: HashMap;
impl Solution {
pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
let mut map=HashMap::new();
for i in 0..nums.len(){
if map.contains_key(&nums[i])&&((map.get(&nums[i]).unwrap()-i) as i32).abs()<=k{
return true;
}else{
map.insert(nums[i],i);
}
}
false
}
}