算法:存在重复元素 II (哈希表和滑动窗口)

2023-12-14 14:47:20

?哈希表 时间复杂度 O(n) 空间复杂度 O(n)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
    let map = new Map()
    for (let [index, item] of nums.entries()) {
        if (!map.has(item)) {
            map.set(item, index)
        } else {
            if (Math.abs(index - map.get(item))<=k){
                return true
            }else{
                 // 更新哈希表中重复元素的索引为当前索引
                 map.set(item, index)
            }
        }
    }
    return false
};

? 滑动窗口?时间复杂度 O(n) 空间复杂度 O(k)

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
    let set = new Set()
    for(let [index,item] of nums.entries()){
        // 如果遍历的元素已经超过窗口边界就把窗口向右移1位
        if(index > k){
            set.delete(nums[index-k-1])
        }
        if(!set.has(item)){
            set.add(item)
        }else{
            return true
        }
    }
    return false
};

文章来源:https://blog.csdn.net/sdhshsjh/article/details/134992186
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。