美文网首页
存在重复元素 II

存在重复元素 II

作者: 422ccfa02512 | 来源:发表于2020-12-10 21:34 被阅读0次

题目描述

难度级别:简单

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

解题思路

哈希表

嗯。。。简单无脑。。。判断哈希表中是否存在当前元素的key,若存在,判断2者值相差是否大于k,若大于则覆盖值,若小于则输出true。

const containsNearbyDuplicate = function(nums, k) {
    const hashMap = new Map()

    for (let i = 0; i < nums.length; i++) {
        const v = hashMap.get(nums[i])
        
        if (v && i + 1 - v <= k)
            return true
        else
            hashMap.set(nums[i], i + 1)
    }

    return false
};

集合

将元素存储于集合中,若集合中数量大于k,将集合第一个元素删除。在此情况下,若在集合中找到当前值,输出true。

const containsNearbyDuplicate = function(nums, k) {
    const set = new Set()

    for (let i = 0; i < nums.length; i++) {
        if (set.has(nums[i])) return true
        set.add(nums[i])
        if (set.size > k) set.delete(nums[i - k])      
    }

    return false
};

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/contains-duplicate-ii

相关文章

网友评论

      本文标题:存在重复元素 II

      本文链接:https://www.haomeiwen.com/subject/nunrgktx.html