Contain Duplicate II

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 difference between i and j is at most k.

Analyse:

1. For every element in the array, find if other elements meet its requirement.

Time Limited Exceeded.

 1 class Solution {
 2 public:
 3     bool containsNearbyDuplicate(vector<int>& nums, int k) {
 4         if(nums.size() <= 1) return 0 <= k;
 5         
 6         for(int i = 0; i < nums.size(); i++){
 7             for(int j = i + 1; j <= i + k; j++){
 8                 if(nums[j] == nums[i]) return true;
 9             }
10         }
11         return false;
12     }
13 };

View Code

2. As long as one of the element in the remaining part satisfy the condition, we can return true.

Runtime: 32ms.

 1 class Solution {
 2 public:
 3     bool containsNearbyDuplicate(vector<int>& nums, int k) {
 4         unordered_map<int, int> up;
 5         for(int i = 0; i < nums.size(); i++){
 6             if(up.find(nums[i]) != up.end() && i - up.find(nums[i])->second <= k) return true;
 7             else up[nums[i]] = i;
 8         }
 9         return false;
10     }
11 };