Question

219. 存在重复元素 II

English Version

题目描述

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引_ _i 和_ _j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

 

示例 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

 

 

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

解法

方法一：哈希表

我们用哈希表 $d$ 存放最近遍历到的数以及对应的下标。

遍历数组 nums，对于当前遍历到的元素 $nums[i]$，如果在哈希表中存在，并且下标与当前元素的下标之差不超过 $k$，则返回 true，否则将当前元素加入哈希表中。

遍历结束后，返回 false。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 nums 的长度。

class Solution:
  def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    d = {}
    for i, x in enumerate(nums):
      if x in d and i - d[x] <= k:
        return True
      d[x] = i
    return False

class Solution {
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < nums.length; ++i) {
      if (i - d.getOrDefault(nums[i], -1000000) <= k) {
        return true;
      }
      d.put(nums[i], i);
    }
    return false;
  }
}

class Solution {
public:
  bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int, int> d;
    for (int i = 0; i < nums.size(); ++i) {
      if (d.count(nums[i]) && i - d[nums[i]] <= k) {
        return true;
      }
      d[nums[i]] = i;
    }
    return false;
  }
};

func containsNearbyDuplicate(nums []int, k int) bool {
  d := map[int]int{}
  for i, x := range nums {
    if j, ok := d[x]; ok && i-j <= k {
      return true
    }
    d[x] = i
  }
  return false
}

function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const d: Map<number, number> = new Map();
  for (let i = 0; i < nums.length; ++i) {
    if (d.has(nums[i]) && i - d.get(nums[i])! <= k) {
      return true;
    }
    d.set(nums[i], i);
  }
  return false;
}

public class Solution {
  public bool ContainsNearbyDuplicate(int[] nums, int k) {
    var d = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; ++i) {
      if (d.ContainsKey(nums[i]) && i - d[nums[i]] <= k) {
        return true;
      }
      d[nums[i]] = i;
    }
    return false;
  }
}

class Solution {
  /**
   * @param Integer[] $nums
   * @param Integer $k
   * @return Boolean
   */
  function containsNearbyDuplicate($nums, $k) {
    $hashtable = [];
    for ($i = 0; $i < count($nums); $i++) {
      $tmp = $nums[$i];
      if (array_key_exists($tmp, $hashtable) && $k >= $i - $hashtable[$tmp]) {
        return true;
      }
      $hashtable[$tmp] = $i;
    }
    return false;
  }
}