知识点

哈希,枚举

思路

首先,我们使用map<int,vector>来建立点的编号到对应编号所在的位置之间的映射(有序):

对样例:1 2 3 1

int(编号) vector(所在位置集合)
1 0,3
2 1
3 2

然后,对每个相同编号的vector进行遍历,若存在vector[i]-vector[i-1]<=K,则说明题意所求存在,返回true。否则不存在,返回false

代码

                                                                                #include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param weights int整型vector 
     * @param n int整型 
     * @param k int整型 
     * @return bool布尔型
     */
    bool checkDuplicate(vector<int>& weights, int n, int k) {
        // write code here
        map<int,vector<int>>t;

        for(int i=0;i<n;i++)
        {
            t[weights[i]].push_back(i);
        }

        for(auto v:t)
        {
            for(int i=1;i<v.second.size();i++)
            {   // cout<<v.first<<"  "<<v.second[i]<<"   "<<v.second[i-1]<<endl;
                if(v.second[i]-v.second[i-1]<=k)return true;
            }
        }
        return false;
    }
};
                                                                                ```