LeetCode - Contains Duplicate II

LeetCode 的 Contains Duplicate II 題目如下:

Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.


簡單說他要的是要一個功能,當給予一個整數陣列與一個整數值 k,能找出兩個不同的索引值,這兩個索引值的差距最多為 k,且其對應到的整數陣列的值是相同的。


這邊筆者是用迴圈搭配 Dictionary 來處理,每跑一個數就去判斷 Dictionary 是否有含有一樣的數值,如果有則去判斷索引值的差距是否在 k 內,是的話則回傳 true。如果不是或是數值不存在在 Dictionary 內,則將其加入或是將 Dictionary 中的索引值更新,便於後續查找。如果整個陣列跑完都找不到結果,將 false 回傳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public bool ContainsNearbyDuplicate(int[] nums, int k) {
var length = nums.Length;
var dict = new Dictionary<int, int>();
for(var idx = 0; idx < length; ++idx)
{
var num = nums[idx];
var prevIdx = -1;
if(dict.TryGetValue(num, out prevIdx))
{
if(idx - prevIdx <= k)
return true;
}
dict[num] = idx;
}
return false;
}
}