題目來源
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.
第一想法就是把每種情況都列一下，復(fù)雜度O(kn)。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        for (int i=0; i<n-1; i++)
            for (int j=i+1; j<=i+k && j<n; j++)
                if (nums[i] == nums[j])
                    return true;
        return false;
    }
};

不出意外TLE了。
然后又想了想，用哈希，記錄下每個(gè)數(shù)字出現(xiàn)的位置。

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

看了看答案，發(fā)現(xiàn)只要記錄k個(gè)就可以了，里面有重復(fù)的就true。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int n = nums.size();
        for (int i=0; i<n; 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;
    }
};