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 difference between i and j is at most k.

Subscribe to see which companies asked this question
Tags: Array, Hash Table
Similar Problems: Contains Duplicate, Contains Duplicate III

题目要求判断给定数组中，是否存在重复的数且重复的数的位序差小于给定的K。
思路一（有错）：

超时的解法：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int size_nums = nums.size();
        if(size_nums <= 1) return false;
        //if(size_nums - 1  k)
        int diff = 0;
        
        bool flag = false;
        bool result = false;
        set<int> mp1;
        set<int>::iterator iter1;
        for(int i = 0; i < size_nums; i++)
        {
            mp1.insert(nums[i]);
        }
        
        vector<vector<int>> sequence1;
        vector<int> temp;
        for(iter1 = mp1.begin(); iter1 != mp1.end(); iter1++)
        {
            temp.clear();
            for(int j = 0; j < size_nums; j++)
            {
                if(nums[j] == *iter1)
                    temp.push_back(j);
            }
            sequence1.push_back(temp);
        }
        
        for(int i = 0; i < sequence1.size(); i++)
        {
            temp.clear();
            temp = sequence1[i];
            int size_temp = temp.size();
            if(size_temp == 1) continue;
            
            int diff2 = temp[1] - temp[0];
            for(int j = 1; j < size_temp; j++)
            {
                if((temp[j] - temp[j-1]) < diff2)
                {
                    diff2 = (temp[j] - temp[j-1]);
                    cout << diff2;
                }
            }
            
            if(diff == 0) diff = diff2;
            cout << " " << diff << endl;
            if(diff2 < diff) diff = diff2;
            cout << " " << diff << endl;
        }
        return (diff != 0) && (diff <= k);
        
        
    }
};

与上面思路一致，使用了数据结构ordered_map的可行解法：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int size_nums = nums.size();
        if(size_nums <= 1) return false;
        
        unordered_map<int, int> mp1;
        for (int i = 0; i < nums.size(); ++i) {
            //扫描一遍数组，如果首次出现，将元素和位序加入map
            //如果找到了（即重复出现），比较当前位序与该元素上次出现时的位序，若差不大于k，返回true
            //若不满足，将map中该重复数字的值更新为当前位序
            //算法时间复杂度：O(n)，其中map的find函数为O(logn)
            if (mp1.find(nums[i]) != mp1.end() && i - mp1[nums[i]] <= k) 
            {
                cout << i << " " << mp1[nums[i]] << endl;
                return true;
            }
            else mp1[nums[i]] = i;
        }
        return false;
        
        
    }
};