0217. 存在重复元素 Contains Duplicate

方法1, Brute Force

直接暴力遍历 vector, 查找当前元素是否在后面出现过.

brute-force

这个方法的时间复杂度为 O(n^2). 可想而知, 这个解法是无法通过 leetcode 平台检验的, 结果会超时. 这个方法可以用来查找具体哪些元素是重复的.

#![allow(unused)]
fn main() {
// 两层遍历数组
pub fn contains_duplicate(nums: Vec<i32>) -> bool {
    assert!(!nums.is_empty());
    let len = nums.len();
    for i in 0..(len - 1) {
        for j in (i + 1)..len {
            if nums[i] == nums[j] {
                return true;
            }
        }
    }
    false
}
}

方法2, 先排序, 再遍历

既然暴力遍历比较慢, 那能不能加快一些? 如果我们先给 vector 做排序, 然后应该只需要遍历它一次, 每个元素与相邻的元素比较是否相等, 就可以判定是否包含重复的元素.

sort-first

这个方法的时间复杂度为 O(nlogn), 它还可以用来查找具体哪些元素是重复的.

#![allow(unused)]
fn main() {
// 先排序, 再遍历
pub fn contains_duplicate2(nums: Vec<i32>) -> bool {
    assert!(!nums.is_empty());
    let mut nums = nums;
    // 先排序
    nums.sort();
    let len = nums.len();
    for i in 0..(len - 1) {
        if nums[i] == nums[i + 1] {
            return true;
        }
    }
    false
}
}

方法3, 使用 HashSet 缓存数值

考虑到集合 (HashSet) 快速能查找元素的特性(时间是O(1)), 我们可以用它来存储元素, 加快查找.

先遍历整个数组, 查找集合中是否存在该元素, 如果存在就返回, 如果不存在就把它插入到集合中.

hash-set

这个方法的时间复杂度为 O(nlogn), 空间复杂度为 O(n), 它还可以用来查找具体哪些元素是重复的.

#![allow(unused)]
fn main() {
// 使用 Hash Set 存放访问过的数组中的元素.
pub fn contains_duplicate3(nums: Vec<i32>) -> bool {
    if nums.len() < 2 {
        return false;
    }
    let mut cache = HashSet::with_capacity(nums.len());
    for &num in nums.iter() {
        // 如果 insert() 返回 false, 就说明 cache 之前已经包含 num 了; 说明 num 是重复的元素.
        if !cache.insert(num) {
            return true;
        }
    }
    false
}
}

方法4, 使用 HashSet 缓存所有数值

上面的方法3已经足够好了. 但是, 我们仔细考虑题目, 发现它并不要求我们找到究竟是哪些元素是重复的.

基于此, 我们可以对方法3做一下修改:

遍历整个数组, 将里面的所有元素都插入到集合中
比较集合中元素的个数是否与数组中元素的个数相同, 如果不同, 那就说明有重复元素