# 0219. 存在重复元素 II

### 题目地址(219. 存在重复元素 II)

<https://leetcode-cn.com/problems/contains-duplicate-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

```

### 前置知识

* hashmap

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

用一个 hashmap 存储已经访问过的数字，每次访问都查看 hashmap 中是否有这个元素，有的话拿出索引进行比对，是否满足条件（相隔不大于 k），如果满足返回 true 即可。

可以看出，这道题就是两数和的进阶版。大家可以将这两道题结合起来理解哦\~

### 公司

* airbnb
* palantir

### 关键点解析

* 空间换时间

### 代码

* 语言支持：JS，Python，C++, Java

Javascript Code:

```js
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function (nums, k) {
  const visited = {};
  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    if (visited[num] !== undefined && i - visited[num] <= k) {
      return true;
    }
    visited[num] = i;
  }
  return false;
};
```

Python Code:

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

C++ Code：

```
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        auto m = unordered_map<int, int>();
        for (int i = 0; i < nums.size(); ++i) {
            auto iter = m.find(nums[i]);
            if (iter != m.end()) {
                if (i - m[nums[i]] <= k) {
                    return true;
                }
            }
            m[nums[i]] = i;
        }
        return false;
    }
};
```

Java Code:

```java
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++)
        {
            if(map.get(nums[i]) != null && (i-map.get(nums[i])) <= k)
            {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/ndzy7w.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/219.contains-duplicate-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.