219. 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.

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

---

本题是LeetCode Contains Duplicate的升级版，要求是判断是否有距离不超过k的两个相同的数。
首先想到暴力方法，一种是直接两层长度为n的循环，判断是否有距离不超过k的两个相等的数，另一种是外层循环为n，内层只要循环长度k，因为即使超过k有相等数的，也不符合题意。尝试之后显然超时。
然后我想到了另一种方法，把数组中所有相同数字的下标都放到一个桶里，后续再在这个桶里看是否有距离不超过k的两个下标对；如果桶里只有一个下标，说明这个下标对应的数没有重复出现，直接continue。完整代码如下：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        if (nums.size() == 0)
            return false;
        unordered_map<int, int> hash_table;
        int distinct_cnt = 1; // 相异元素的个数
        vector<vector<int> > duplicate_indices = { {} }; // 跳过第0个桶
        for (int i = 0; i < nums.size(); i++) {
            if (hash_table[nums[i]] == 0) {
                hash_table[nums[i]] = distinct_cnt++;
                duplicate_indices.push_back({ i });
            }
            else {
                duplicate_indices[hash_table[nums[i]]].push_back(i);
                // 把相同元素的下标都放到一个桶里
            }
        }
        for (int i = 1; i < duplicate_indices.size(); i++) {
            // 查每个桶
            if (duplicate_indices[i].size() < 2)
                continue;
            for (int u = 0; u < duplicate_indices[i].size() – 1; u++) {
                for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
                    if (duplicate_indices[i][v] – duplicate_indices[i][u] <= k)
                        return true;
                }
            }
        }
        return false;
    }
};

本代码提交AC，用时46MS。
后来看欣欣的解法LeetCode Contains Duplicate II，发现这个解法好厉害啊，用到了高级的unordered_set，之前只用过unordered_map，赶紧来学习一下。
她的思路是这样的，题目要求相同元素的距离不超过k，则我们维护一个长度为k的滑动窗口，把这个窗口里的所有数都hash到unordered_set里，后续每来一个元素，去这个hash_set里查之前是否出现过，因为我们的hash_set里只保留了前k个元素，所以如果hash_set查到了，他们的距离肯定是不超过k的。这种解法真是漂亮！完整代码如下：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        if (nums.size() == 0 || k <= 0)
            return false;
        if (k >= nums.size())
            k = nums.size() – 1;
        unordered_set<int> hash_set;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k)
                hash_set.erase(nums[i – k – 1]); // 滑动窗口，删掉窗口第一个元素
            if (hash_set.find(nums[i]) != hash_set.end())
                return true;
            hash_set.insert(nums[i]); // 把新元素插入窗口
        }
        return false;
    }
};

本代码提交AC，用时29MS，果然比我的速度快，厉害~
二刷。用一个hash表记录每个数最近出现的下标，如果新来一个数，之前在hash表中出现过，则看看下标之差是否小于等于k，是则返回true；否则更新hash。
思路非常简单，代码如下：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            if (hash.find(nums[i]) != hash.end() && i – hash[nums[i]] <= k)
                return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};

本代码提交AC，用时35MS。