Leetcode 219. Contains Duplicate II (hashmap 和 sliding window)

219. Contains Duplicate II
     Easy
     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:

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

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

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

Constraints:

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

解法1：就用简单的unordered_map

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

解法2: sliding window

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0, right = 0;
        unordered_set<int> s;
        while (right < n) {
            s.insert(nums[right]);
            right++;
            while (right - left > k) {
                s.erase(nums[left]);
                left++;
            }
            if (right < n && s.find(nums[right]) != s.end()) return true;
        }
        return false;
    }    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18