Implement the containsDuplicateWithinK method that checks whether duplicate values appear within distance k.
The input contains an integer array nums, its length size, and an integer k. Your task is to check whether the same value appears at least twice within a distance of k indexes.
In other words, find two indexes i and j such that nums[i] == nums[j] and |i - j| <= k.
For example, in [1,2,3,1] with k = 3, the value 1 appears at indexes 0 and 3, so the answer is true.
Example 1
Input
nums (int[]) =
[1,2,3,1]size (int) =
4k (int) =
3Returns (boolean)
trueExample 2
Input
nums (int[]) =
[1,0,1,1]size (int) =
4k (int) =
1Returns (boolean)
trueExample 3
Input
nums (int[]) =
[1,2,3,1,2,3]size (int) =
6k (int) =
2Returns (boolean)
falseUse a map to store the most recent index where each number was seen.
When the same number appears again, compare the current index with the stored previous index. If the distance is less than or equal to k, return true.
If the distance is larger, update the stored index because the latest occurrence is more useful for future comparisons.
Pseudocode:
function containsDuplicateWithinK(nums, size, k):
create empty map lastIndex
for i from 0 to size - 1:
value = nums[i]
if value exists in lastIndex:
if i - lastIndex[value] <= k:
return true
lastIndex[value] = i
return falseReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run