Welcome to Subscribe On Youtube
219. Contains Duplicate II
Description
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
Solutions
Solution 1: Hash Table
We use a hash table $d$ to store the nearest index of the number it has visited.
We traverse the array nums
. For the current element $nums[i]$, if it exists in the hash table, and the difference between its index and the current index is no larger than $k$, then return true
. Otherwise, we add the current element into the hash table.
After the traversal, return false
.
The time complexity is $O(n)$ and the space complexity is $O(n)$. Here $n$ is the length of array nums
.
-
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; } };
-
class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: mp = {} for i, v in enumerate(nums): if v in mp and i - mp[v] <= k: return True mp[v] = 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; }
-
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; } }
-
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; } }