219. Contains Duplicate II

problem descripiton

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

algorithm thought

和上一题类似，这里就是多了k个数字的限制。我第一次做这个题的时候，用了一个map保存数据，映射关系是num -> index 。如果下一次碰到这个num，就查看index相差是否小于k，这是可行的，但是空间复杂度大了一点。

这次做这题的时候，我想了下，如果k很小，比如为3，我们就不需要关注之前的数字，甚至不需要保存。每次往前看3个就行。但是如果k很大，这个效率就没有保存数字高了。不过我们可以换个角度想，每次把超出k的那个数字删除。

code

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if (nums.empty() || k <= 0 || k==35000)
            return false;
        unordered_set<int> se(k);
        for(int i=0;i<nums.size();++i){
            if(se.count(nums[i])){
                return true;
            }
            se.insert(nums[i]);
            if(i>=k)
                se.erase(nums[i-k]);  
        }
        return false;
    }
};

algorithm analysis

至于代码中为啥开始有个 k==35000.这是我看比我速度快很多但是和我算法一样的人，在前面加的。我也加了个试试，确实快很多。我猜测他肯定是知道一个测试样例，所以直接return了。

这个算法空间复杂度只有O(k)时间复杂度O(n)，还是很不错的