1. 题目

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

2. 解一

和# 217. 存在重复元素差不多，维护一个哈希表,只不过这次存储的是下标，当遇到相同值是判断两个下标差是否小于k

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
 var containsNearbyDuplicate = function(nums, k) {
  const hashArr = [] 
  for(let i in nums) {
    if(hashArr[nums[i]] === undefined) {
      hashArr[nums[i]] = i
    } else {
      if(i - hashArr[nums[i]] <= k) {
        return true
      } else {
        hashArr[nums[i]] = i
      }
    }
  }
  return false
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)

3. 优化

数组改用Set
每次往Set中Push一个新值，Set的长度始终维持在小于k，如果新的值有在Set中，则直接返回

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
 var containsNearbyDuplicate = function(nums, k) {
  const set = new Set()
  for(let i in nums) {
    if(set.has(nums[i])) {
      return true
    }
    set.add(nums[i])
    if(set.size > k) {
      set.delete(nums[i - k])
    }
  }
  return false
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(k)