[LeetCode] 219. Contains Duplicate II

轉自LeetCode

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= 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

 

Constraints:

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

<Solution>

這題是 217. Contains Duplicate 的衍生題

這次多了一個條件是，相同兩個數字所在的 index 的絕對差值，必須小於等於 k

解題想法是

• 一樣使用 hash set 來記錄每個 index 所在的值

• 把和目前的 index 的差距超過 k 的值，從 hash set 裡面拿掉。這樣檢查的時候，就能確保 index 的絕對差是小於等於 k 的

code 如下

C++

Java

另一個解法是用 sliding window 的概念

當 right 指標不斷向右移的時候，如果發現有重複的數字出現

檢查是否符合條件，是的話就回傳 true

不符合條件，更新 map，繼續找下去

kotlin