Contains Duplicate II

Posted on Edited on In Views:

219.Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.

Example 1:

1
2
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

哈希表：

时间复杂度：O(n)

空间复杂度：O(n)

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

滑动窗口：

时间复杂度：O(n)

空间复杂度：O(k+1)

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