# 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啦。 關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。