存在重复元素 II

题目描述

难度级别：简单

给定一个整数数组和一个整数 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。

代码语言：javascript复制

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。

代码语言：javascript复制

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

编程算法

0 人点赞