Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

**Solution** : this is a typical hash table question. if hash table contains num, return true, otherwise add to hash table.

public bool ContainsDuplicate(int[] nums) { var myDictionary = new Dictionary<int, int>(); foreach(var num in nums) { if(myDictionary.ContainsKey(num)) { return true; } myDictionary.Add(num, 1); } return false; }

**Solution 2**: if you like LINQ, here is one line code.

public bool ContainsDuplicate(int[] nums) { return nums.Count() > nums.Distinct().Count(); }

### Follow-up question:

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.

**Solution** : store index to the hash table so that each time, we found there is previous same value already added to the hash table, just compare the index.

public bool ContainsNearbyDuplicate(int[] nums, int k) { var myDictionary = new Dictionary<int, int>(); for(var i = 0; i < nums.Length; i++) { if(myDictionary.ContainsKey(nums[i])) { if(i - myDictionary[nums[i]] <= k) return true; else myDictionary[nums[i]] = i; } else myDictionary.Add(nums[i], i); } return false; }

**Follow-up question:**

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

**Solution :** since we could not use hash table to do it any more, the obviously way to store the windows set is list. and scan list would take O(K) for each element. we can improve it a little bit by sortedset, which reduce the time to O(lgk).

public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) { var bst = new SortedSet(); if (t < 0) return false; for (int i = 0; i < nums.Length; i++) { if (i - k - 1 >= 0) { bst.Remove(nums[i - k - 1]); } if (bst.GetViewBetween((long)nums[i] - t, (long)nums[i] + t).Any()) return true; bst.Add(nums[i]); } return false; }

**Solution 2:** You can use bucket sort to do it, the key part is choose bucket size. bucket size = t + 1 is good choice since every element in it satisfy the condition. See here for more explanation.

public bool ContainsNearbyAlmostDuplicate3(int[] nums, int k, int t) { var buckets = new Dictionary<long, long>(); if (t < 0) return false; for (int i = 0; i < nums.Length; i++) { var bucketIndex = ((long) nums[i] - int.MinValue)/((long) t + 1); if (i - k - 1 >= 0) { buckets.Remove(((long)nums[i - k - 1] - int.MinValue) / ((long)t + 1)); } if (buckets.ContainsKey(bucketIndex) || buckets.ContainsKey(bucketIndex - 1) && nums[i] - buckets[bucketIndex - 1] <= t || buckets.ContainsKey(bucketIndex + 1) && buckets[bucketIndex + 1] - nums[i] <= t) return true; buckets[bucketIndex] = nums[i]; } return false; }