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] <= 1090 <= k <= 105
Solutions
Solution 1: Hash Table
We use a hash table d to store the recently traversed numbers and their corresponding indices.
Traverse the array nums. For the current element nums[i], if it exists in the hash table and the difference between the indices is no more than k, return true. Otherwise, add the current element to the hash table.
After traversing, return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptJavaScriptC#PHP
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = {}
for i, x in enumerate(nums):
if x in d and i - d[x] <= k:
return True
d[x] = i
return False(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function (nums, k) {
const d = 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;
};(code-box)
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;
}
}(code-box)
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Boolean
*/
function containsNearbyDuplicate($nums, $k) {
$d = [];
for ($i = 0; $i < count($nums); ++$i) {
if (array_key_exists($nums[$i], $d) && $i - $d[$nums[$i]] <= $k) {
return true;
}
$d[$nums[$i]] = $i;
}
return false;
}
}(code-box)
