0219. 存在重复元素II Contains Duplicate II

问题描述

这个问题与 0001. 两数之和 Two Sum 很相似, 而且其解法也都是一样的.

方法1, Brute Force

这个方法比较直接, 就是遍历数组, 并遍历后面的每个元素, 判断它们是否重复.

因为有两层遍历, 这个方法的时间复杂度是 O(n^2).

#![allow(unused)]
fn main() {
// Brute Force
pub fn contains_nearby_duplicate1(nums: Vec<i32>, k: i32) -> bool {
    let len = nums.len();
    let k = k as usize;

    for i in 0..(len - 1) {
        for j in (i + 1)..len {
            if nums[i] == nums[j] && j - i <= k {
                return true;
            }
        }
    }
    false
}
}

方法2, 哈稀表

同样是需要遍历整个数组, 我们可以使用哈稀表缓存一下访问过的元素, 以加快查找元素的时间. 这个哈稀表用于记录元素值到它在数组中的索引值之间的关系.

这个方法的时间复杂度是 O(nlogn).

#![allow(unused)]
fn main() {
// 使用 HashMap
pub fn contains_nearby_duplicate2(nums: Vec<i32>, k: i32) -> bool {
    let k = k as usize;

    // map 用于存储数值及其在数组中的位置
    let mut map = HashMap::<i32, usize>::with_capacity(nums.len());

    // 遍历数组中所有元素
    for (index, &num) in nums.iter().enumerate() {
        // 在 map 中尝试查找这个元素, 并判断与当前遍历的元素是否重复.
        if let Some(&old_index) = map.get(&num) {
            if (index - old_index) <= k {
                return true;
            }
        }
        map.insert(num, index);
    }
    false
}
}