The original article is available at https://dawnmagnet.top/leetcode/2022/01/19/.

Given an integer array nums and an integer k, determine whether there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k. Return true if such a pair exists; otherwise, return false.

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 0 <= k <= 10^5

Source: LeetCode Link: https://leetcode-cn.com/problems/contains-duplicate-ii Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis

#

In plain terms, this problem asks us to find two equal values in an array whose indices are no more than a given distance apart. How can we check this efficiently?

A sliding window solves the problem efficiently. By the problem’s condition, any possible pair must lie within an index range of length k+1. We can maintain a sliding window of length k+1 and use a hash table to detect duplicates, checking for a valid answer only inside that window.

Rust Code

#

impl Solution {
    pub fn contains_nearby_duplicate(mut nums: Vec<i32>, k: i32) -> bool {
        let k = k as usize;
        let mut map = std::collections::HashMap::new();
        for i in 0..nums.len() {
            if i > k {
                *map.entry(nums[i - k - 1]).or_insert(0) -= 1;
            }
            *map.entry(nums[i]).or_insert(0) += 1;
            if *map.entry(nums[i]).or_insert(0) > 1 {
                return true;
            }

        }
        return false;
    }
}