Leetcode 219. 存在重复元素 II

说明：

　　首先，这是一道Easy题，我天！但是题意理解还是很多坑~

题目描述：

　　给定一个整数数组和一个整数 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

理解：

　　寻找每个元素最先出现的位置和最终出现的位置，如果i和j不同，取其绝对值，看是否可以达到k，如果等于k，说明满足题意！

 struct node {

     int max = -;

     int min = -;

 };

 bool containsNearbyDuplicate_bak(vector<int>& nums, int k) {

     //两个map，一个存最小下标，一个存最大下标

     map<int, int> mp;  //用于统计出现的字符个数

     map<int, node> maxDisMap;  //用于存放距离

     int i,res=;

     for (i = ; i<nums.size(); i++)

     {

         mp[nums[i]]++;

         if (mp[nums[i]] == )

         {

             //首次出现，存入距离

             maxDisMap[nums[i]].min = i;

         }

         else if (mp[nums[i]] > ) {

             maxDisMap[nums[i]].max = i;

         }

     }

     //遍历数组中的最大最小值的差值

     map<int, node>::iterator it;

     for (it = maxDisMap.begin(); it != maxDisMap.end(); it++)

     {

         if (it->second.max - it->second.min > res)

             res = it->second.max - it->second.min;

     }

     if (res == k)

         return true;

     return false;

 }

　　那么问题来了，对于示例2而言，第一个1出现的位置索引是0，最后一个出现的位置索引是3，其差的最大绝对值为3，大于给定的k，为什么返回true？？？

　　发现讨论区里也有很多类似的问题在讨论

　　这样看来，只要保证存在小于等于k的两个绝对值的差，即可，修改代码如下：

 bool containsNearbyDuplicate(vector<int>& nums, int k) {

     //两个map，一个存最小下标，一个存最大下标

     map<int, int> mp;  //用于统计出现的字符个数

     map<int, node> maxDisMap;  //用于存放距离

     int i, res = INT_MAX;

     for (i = ; i<nums.size(); i++)

     {

         mp[nums[i]]++;

         if (mp[nums[i]] == )

         {

             //首次出现，最大最小都存起来

             maxDisMap[nums[i]].min = i;

             maxDisMap[nums[i]].max = i;

         }

         else if (mp[nums[i]] == ) {

             maxDisMap[nums[i]].max = i;  //更新最大值

             if (maxDisMap[nums[i]].max - maxDisMap[nums[i]].min <= k)

                 return true;

         }

         else {

             maxDisMap[nums[i]].min = maxDisMap[nums[i]].max;  //往后推，只记录相邻的两个相同值

             maxDisMap[nums[i]].max = i;

             if (maxDisMap[nums[i]].max - maxDisMap[nums[i]].min <= k)

                 return true;

         }

     }

     return false;

 }

　　等待学习新的方法~~~

巴特西

Leetcode 219. 存在重复元素 II

最新文章

热门文章