# LeetCode Easy 219. Contains Duplicate II

tags: leetcode

問題

• Explore
• Problems

アイデア

｢kという整数と整数の配列を与えられたとき，i-j=kかつnums[i]==nums[j]となるようなiとjとなるものがあるかどうかを探す｣問題です．

解法

• 連想配列を用意します．(map[num[index]] = index)
• 0 <= i < nums.len()となるようなiを走査します．
  • そして，map.get(num[i])を取得します(つまり，nums[i]に対応した添字j．
    • 取得できないときは，map.insert(nums[i], i)とします．
  • できたときは，i - j <= kとなれば，これは求める数字があるということです．
• 全て調べて無理な時はfalseです．

計算量

配列の大きさを$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Rust

use std::collections::HashMap;

impl Solution {
  pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
    let k = k as usize;
    let mut map = HashMap::new();
    
    for i in 0..nums.len() {
      if let Some(j) = map.get((&nums[i])) {
        if i - j <= k {
          return true;
        }
      }
      map.insert(nums[i], i);
    }
    false
  }
}