讨论/《哈希表》 - 存在重复元素 II/
《哈希表》 - 存在重复元素 II
共 7 个回复

JavaScript版本~

使用map存储已经遍历过的字符,将字符映射到当前字符的索引

如果后续的遍历中遇到相同的字符,则判断 当前索引 - map中已存在的字符所映射的索引值 < k 是否成立

看到其他人的解法都用了abs函数做结对值,由于后续的索引一定会大于之前存储的索引值, 其实并不需要使用abs函数取绝对值来判断

var containsNearbyDuplicate = function (nums, k) {
    const map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (!map.has(nums[i])) map.set(nums[i], i)
        else {
            if (i - map.get(nums[i]) <= k) return true
            else map.set(nums[i], i)
        }
    }
    return false
};
1

维护一个最长为k的hash_set就好了

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> set;
        for(int i = 0; i < nums.size(); i++){
            if(set.count(nums[i])) return true;
            set.insert(nums[i]);
            if(set.size() > k){
                set.erase(nums[i - k]);
            }
        }
        return false;
    }
};
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for (int i = 0; i < nums.size(); ++i) {
            if (map.count(nums[i]) > 0 && i-map[nums[i]] <= k) {
                    return true;
            } else {
                map[nums[i]] = i;   //if notexist record index, otherwise update index
            }
        }
        return false;
    }
};

c++
水题

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++)
        {
            if(mp.find(nums[i])==mp.end())//若哈希表中没有此数据
            {
                mp[nums[i]]=i;
            }
            else if(mp.find(nums[i])!=mp.end())
            {
                if(abs(mp[nums[i]]-i)<=k) return true;
                else mp[nums[i]]=i;
            }
        }
        return false;
    }
};
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int ,int> map;
        for (int i = 0; i < nums.size(); i++) {
            if (map.count(nums[i]) && abs(map[nums[i]] - i) <= k) {
                    return true;
            }
                map[nums[i]] = i;
        }
        return false;
    }
};
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        //创建哈希映射
        unordered_map<int, int> hashmap;
        int size = nums.size();
        for(int i = 0; i < size; i++){
            if(hashmap.find(nums[i]) != hashmap.end()){
                //如果小于k,输出true
                if(abs(i - hashmap[nums[i]]) <= k){
                    return true;
                }
                //擦除当前相同值
                hashmap.erase(hashmap[nums[i]]);
                //填入重复值的新索引
                hashmap[nums[i]] = i;
            }
            else{
                //哈希表中没有,加入
                hashmap[nums[i]] = i;
            }
        }
        return false;
    }
};

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