Contains-Duplicate-II

LeetCode
,

第74天。

今天的题目是Contains 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 absolute difference between i and j is at most k.

显然这道题目可以用两个循环去实现，但是这样会超时，效率不高。

这里是用Hash Table去做的,key存储nums[i],value存储i,这样我们用O(n)的时间就可以完成了。

1
2
3
4
5
6
7
8
bool containsNearbyDuplicate(vector<int>& nums, int k) {
    unordered_map<int,int> m;
    for(int i = 0;i < nums.size();i++) {
        if (m.find(nums[i]) != m.end() && m[nums[i]] + k >= i) return true;
        m[nums[i]] = i;
    }
    return false;
}

dicuss中的做法是用unordered_set去做的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
    unordered_set<int> s;

    if (k <= 0) return false;
    if (k >= nums.size()) k = nums.size() - 1;

    for (int i = 0; i < nums.size(); i++)
    {
        if (i > k) s.erase(nums[i - k - 1]);
        if (s.find(nums[i]) != s.end()) return true;
        s.insert(nums[i]);
    }

    return false;
}