219. Contains Duplicate II Easy

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

Approach

Input: An integer array nums and an integer k

Output: Check whether there are two equal numbers in the array with a distance of less than or equal to k

This is an Array + Hash Table problem.

• We can use a hash table to store the coordinates of the iterated numbers.
• When the distance between the coordinates of a newly iterated number and the same number in the hash table is less than or equal to k, return True.
• Otherwise, update the current number's index in the hash table.
• If no match is found after traversing, return False.

Implementation

python

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # Create a hash table to record the last seen position of each number
        index_map = {}

        # Traverse the array
        for i, num in enumerate(nums):
            # If the current number has appeared before and the index distance is <= k, return True
            if num in index_map and i - index_map[num] <= k:
                return True

            # Update the index of the current number
            index_map[num] = i

        # If no repeating number meeting the conditions is found after traversal, return False
        return False

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    const indexMap = {};

    for (let i = 0; i < nums.length; i++) {
        if (indexMap[nums[i]] != null) {
            if (i - indexMap[nums[i]] <= k) {
                return true;
            }
        }

        indexMap[nums[i]] = i;
    }

    return false;
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Links

219. Contains Duplicate II (English)219. 存在重复元素 II (Chinese)