每天一算：Contains Duplicate II

 1// 219. Contains Duplicate II
 2// https://leetcode.com/problems/contains-duplicate-ii/description/
 3// 时间复杂度: O(n)
 4// 空间复杂度: O(k)
 5class Solution {
 6public:
 7    bool containsNearbyDuplicate(vector<int>& nums, int k) {
 8
 9        if(nums.size() <= 1)  return false;
10
11        if(k <= 0)  return false;
12
13
14        unordered_set<int> record;
15        for(int i = 0 ; i < nums.size() ; i ++){
16
17            if(record.find(nums[i]) != record.end()){
18                return true;
19            }
20
21            record.insert(nums[i]);
22
23            // 保持record中最多有k个元素
24            // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
25            if(record.size() == k + 1){
26                record.erase(nums[i - k]);
27            }
28        }
29
30        return false;
31    }
32};