219.-contains-duplicate-ii.md

219. Contains Duplicate II

LeetCode 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

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

Tags

Array, Hash Table

Solution

We initialize a map as a sliding window to store exactly k values. Iterate over nums, and if window[num] exists, return true. store the current value to window and delete the value from window by key nums[i-k]. Finally, we return false since no qualified element found.

Complexity

• Time complexity: $$O(n)$$
• Space complexity: $$O(k)$$

Code

func containsNearbyDuplicate(nums []int, k int) bool {
	window := map[int]bool{} // num:exist
	for i, num := range nums {
		if window[num] {
			return true
		}
		window[num] = true
		if i >= k {
			delete(window, nums[i-k])
		}
	}
	return false
}