# 0219. 存在重复元素 II ## 题目地址(219. 存在重复元素 II) <https://leetcode-cn.com/problems/contains-duplicate-ii/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个整数数组和一个整数 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++ Javascript Code: ``` <pre class="calibre18">``` <span class="hljs-title">/* * @lc app=leetcode id=219 lang=javascript * * [219] Contains Duplicate II * * https://leetcode.com/problems/contains-duplicate-ii/description/ * * algorithms * Easy (34.75%) * Total Accepted: 187.3K * Total Submissions: 537.5K * Testcase Example: '[1,2,3,1]\n3' * * Given an array of integers and an integer k, find out whether there are two * distinct indices i and j in the array such that nums[i] = nums[j] and the * absolute difference between i and j is at most k. * * * Example 1: * * * Input: nums = [1,2,3,1], k = 3 * Output: true * * * * Example 2: * * * Input: nums = [1,0,1,1], k = 1 * Output: true * * * * Example 3: * * * Input: nums = [1,2,3,1,2,3], k = 2 * Output: false * * * * * */</span> <span class="hljs-title">/** * @param {number[]} nums * @param {number} k * @return {boolean} */</span> <span class="hljs-keyword">var</span> containsNearbyDuplicate = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">nums, k</span>) </span>{ <span class="hljs-keyword">const</span> visited = {}; <span class="hljs-keyword">for</span>(<span class="hljs-keyword">let</span> i = <span class="hljs-params">0</span>; i < nums.length; i++) { <span class="hljs-keyword">const</span> num = nums[i]; <span class="hljs-keyword">if</span> (visited[num] !== <span class="hljs-params">undefined</span> && i - visited[num] <= k) { <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } visited[num] = i; } <span class="hljs-keyword">return</span> <span class="hljs-params">false</span> }; ``` ``` Python Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">containsNearbyDuplicate</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -> bool:</span> d = {} <span class="hljs-keyword">for</span> index, num <span class="hljs-keyword">in</span> enumerate(nums): <span class="hljs-keyword">if</span> num <span class="hljs-keyword">in</span> d <span class="hljs-keyword">and</span> index - d[num] <= k: <span class="hljs-keyword">return</span> <span class="hljs-keyword">True</span> d[num] = index <span class="hljs-keyword">return</span> <span class="hljs-keyword">False</span> ``` ``` C++ Code： ``` <pre class="calibre18">``` <span class="hljs-keyword">class</span> Solution { <span class="hljs-keyword">public</span>: <span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">containsNearbyDuplicate</span><span class="hljs-params">(<span class="hljs-params">vector</span><<span class="hljs-keyword">int</span>>& nums, <span class="hljs-keyword">int</span> k)</span> </span>{ <span class="hljs-keyword">auto</span> m = <span class="hljs-params">unordered_map</span><<span class="hljs-keyword">int</span>, <span class="hljs-keyword">int</span>>(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-params">0</span>; i < nums.size(); ++i) { <span class="hljs-keyword">auto</span> iter = m.find(nums[i]); <span class="hljs-keyword">if</span> (iter != m.end()) { <span class="hljs-keyword">if</span> (i - m[nums[i]] <= k) { <span class="hljs-keyword">return</span> <span class="hljs-params">true</span>; } } m[nums[i]] = i; } <span class="hljs-keyword">return</span> <span class="hljs-params">false</span>; } }; ``` ``` **复杂度分析** - 时间复杂度：O(N)O(N)O(N) - 空间复杂度：O(N)O(N)O(N) 更多题解可以访问我的LeetCode题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经37K star啦。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。