219. Contains Duplicate II

發表於 | 分類於

problem

solution

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

analysis

  • time complexity O(nlogn)
  • speed complexity O(n)