219. Contains Duplicate II #

Problem #

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

Problem Summary #

This is an easy problem. If there are duplicate numbers in the array, and the difference between the indices of the duplicate numbers is less than or equal to K, output true. If there are no duplicate numbers or the index difference exceeds K, output false.

Solution Ideas #

For this problem, you can maintain a map with only K elements. Each time, you only need to check whether this element exists in the map. If it exists, it means the index difference of the duplicate number is within K. If the length of the map exceeds K, delete the element at i-k, thus continuously maintaining only K elements in the map.

Code #

package leetcode

func containsNearbyDuplicate(nums []int, k int) bool {
	if len(nums) <= 1 {
		return false
	}
	if k <= 0 {
		return false
	}
	record := make(map[int]bool, len(nums))
	for i, n := range nums {
		if _, found := record[n]; found {
			return true
		}
		record[n] = true
		if len(record) == k+1 {
			delete(record, nums[i-k])
		}
	}
	return false
}