Question
Formatted question description: https://leetcode.ca/all/219.html
219. Contains Duplicate II
Level
Easy
Description
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
Solution
Use a Map to store each number and the last index at which the number occurred. Loop over the array from left to right. At each index, obtain the number at the current index and find the last index of the number. If the number has already occurred before and the difference between the current index and the previous index is less than or equal to k, then return true. If there isn’t such a number that has its two occurrences differing by k at most, then return false.
Code
Java
import java.util.HashMap;
import java.util.Map;
public class Contains_Duplicate_II {
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
// value => index
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) { // If there are three repeats, then put to the map, and discard the first one
return true;
}
map.put(nums[i], i);
}
return false;
}
}
}