Li Kou daily question - day 29 -219 Duplicate Element II exists

2022.6.3 Did you brush the questions today ？

---

subject ：

Give you an array of integers nums And an integer k , Determine whether there are two... In the array Different indexes i and j , Satisfy nums[i] == nums[j] And abs(i - j) <= k . If there is , return true ; otherwise , return false .

analysis ：

In an array , There is a repeating element , The number of them >=2, What we need to do is to judge whether the lowest subscript difference of this repeating element meets the requirements of the topic k, There are the following special cases

0,1,2,0,0

This situation , The minimum difference of repeated elements is 1, That is, the difference between the last two subscripts of the array

therefore , The conclusion idea is the simplest violent solution , We iterate through the array in turn , Find the subscript difference between each repeating element , And then use it min Function to find the minimum , Then we can make a comparison and make a judgment .

analysis ：

1. Violent solution

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

2. Hashtable

For the array repeating element problem , Hash tables are a good thing ！！！

We can traverse the array once , Each time, the data is traversed according to （ The number , Subscript ） Deposit in map, Then the next time you traverse it, you can judge map Whether the element already exists in it , If it exists and the subscript condition is met, it directly returns true, Otherwise, continue to insert

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> map;

        for (auto i=0;i<nums.size();i++)
        {
            int num = nums[i];
            if (map.count(num) && i - map[num] <= k)
            {
                return true;
            }
            map[num] = i;
        }
        return false;

    }
};

3. The sliding window

thought ： Given k, Then I just need to judge k+1 Whether there are duplicate elements in the number , If there is , It must return true, If it doesn't exist , Then the window moves , The first element is deleted , Insert the last element , Again, determine whether there are duplicate values .

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