Contains Duplicates I,II,III.

Three similar questions.

• 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.

bool containsDuplicate(vector<int>& nums){
  unordered_map<int,int> hash;
  for(int i = 0; i < nums.size(); i++){
    hash[nums[i]]++;
    if(hash[nums[i]] > 1) return true;
  }
  return false;
}

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

No.1

bool containsNearbyDuplicate(vector<int>& nums, int k) {
  unordered_map<int,int> hash;
  bool exist = false;
  for(int i = 0; i < nums.size() && !exist; i++){
    if(hash[nums[i]] != i+1 && hash[nums[i]] > 0) exist = hash[nums[i]]-1+k >= i;
    hash[nums[i]] = i+1;
  }
  return exist;
}

No.2

bool containsNearbyDuplicate(vector<int>& nums, int k) {
  unordered_set<int> hash;
  for(int i = 0; i < nums.size(); i++){
    if(hash.find(nums[i]) != hash.end() ) return true;
    hash.insert(nums[i]);
    if(i >= k) hash.erase(nums[i-k]);
  }
  return false;
}

• Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.
  No.1 Not a good solution, just a start. This method did not consider the case when t is very large as the time complexity is O(N*t).

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t){
  unordered_map<int,int> hash;
  bool exist = false;
  for(int i = 0; i < nums.size() && !exist; i++){
    int temp = nums[i] - t;
    while(hash[temp] == 0 && temp < nums[i]) temp++;
    if(temp < nums[i]) exist = (hash[temp]-1+k >= i);
    if(temp == nums[i] && hash[nums[i]] != i+1 && hash[nums[i]] > 0) exist = hash[nums[i]]-1+k >= i;
    temp = nums[i]+t;
    while(!exist && temp > nums[i] && hash[temp] == 0) temp--;
    if(!exist && temp > nums[i]) exist = (hash[temp]-1+k >= i);
    hash[nums[i]] = i+1;
  }
  return exist;
}

No.3

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t){
  if(t<0) return false;
  unordered_map<int,int> hash;
  int bucket = t+1;
  for(int i = 0; i < nums.size(); i++){
    int index = nums[i] < 0 ? (nums[i]/bucket - 1) : nums[i]/bucket;
    if(hash.find(index) != hash.end()) return true;
    if(hash.find(index-1) != hash.end() && abs(nums[i] - hash[index-1]) < bucket) return true;
    if(hash.find(index+1) != hash.end() && abs(nums[i] - hash[index+1]) < bucket) return true;
    hash[index] = nums[i];
    if(i >= k){
      index = nums[i-k] < 0 ? (nums[i-k]/bucket - 1) : nums[i-k]/bucket;
      hash.erase(hash.find(index));
    }
  }
  return false;
}