LeetCode--219. 存在重复元素 II（C++描述）

迈不过友情╰ 2022-09-14 01:48 177阅读 0赞

// Source : https://leetcode-cn.com/problems/contains-duplicate-ii/  
// Date : 2021-09-30

题目描述：  
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums \[i\] = nums \[j\]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = \[1,2,3,1\], k = 3  
输出: true  
示例 2:

输入: nums = \[1,0,1,1\], k = 1  
输出: true  
示例 3:

输入: nums = \[1,2,3,1,2,3\], k = 2  
输出: false

题目分析：首先还是想通过改进的双重for循环解决问题，即，内层for循环只走到k的大小，但是依旧显示超时，因此必须更换方法，考虑使用hash表进行已有元素及其对应下标的存储，然后继续向后遍历数组，如果碰到与当前数据相同的数据，就计算二者下标的差值的绝对值，如果小于等于k，就返回true，否则继续将该元素的下标存入hash表（也就是覆盖掉之前的<key, index>以备下一次查找使用）

代码：

class Solution 
    {
        
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) 
        {
        
            map<int, int> hash;
            for(int i = 0; i < nums.size(); ++i) 
            {
        
                //如果元素不在哈希表中，就将元素放入哈希表，并放入其下标，即哈希表组织结构为<key, index>
                if(hash.find(nums[i]) == hash.end()) 
                    hash[nums[i]] = i;
                else 
                {
        
                    //如果差值绝对值小于k，返回true
                    if(abs(hash[nums[i]] - i) <= k) 
                        return true;
                    //如果差值过大，则将该元素以及对应的下标继续存入哈希表
                    //以便继续查找之后会不会存在index小于等于k的情况
                    else 
                        hash[nums[i]] = i;
                }
            }
            return false;
        }
    }; 
            //如愿以偿超时
    
            // for(int i = 0;i < nums.size() - 1;++i)
            // {
        
            //     int count = 0;
            //     for(int j = i + 1;count < k && j < nums.size();++j, ++count)
            //     {
        
            //         //滑动窗口的大小就是count
            //         if(nums[i] == nums[j])
            //             return true;
            //     }
            // }
            // return false;