leetcode【219】存在重复元素II 题理解了半天

女爷i 2021-10-03 01:42 254阅读 0赞

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

自己的解法：

class Solution {
         public boolean containsNearbyDuplicate(int[] nums, int k) {
            int res = 0;
            LinkedList<Integer> list = new LinkedList<>();
            Map<Integer,Integer> map = new HashMap<>();
            for(int i = 0;i<nums.length;i++){
                if(map.containsKey(nums[i])){
                    res = i-map.get(nums[i]);
                     map.put(nums[i],i);
                    list.add(res);
                }else
                    map.put(nums[i],i);
            }
            for (int i = 1; i <= k; i++) {
       if (list.contains(i)) { return true;
        }
                }
        return false;
    
        }
    }

维护K大小的哈希表

public boolean containsNearbyDuplicate(int[] nums, int k) {
            Set<Integer> set = new HashSet<>();
            for(int i = 0;i<nums.length;i++){
                if(set.contains(nums[i]))
                    return true;
                set.add(nums[i]);
                if(set.size()>k){
                    set.remove(nums[i-k]);
                }
            }
            return false;
        }

看图理解第二种，巧妙的一批。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 4][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70]: /images/20211003/0f55076c2ab946d0946547ffff856299.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 1]: /images/20211003/e670e1f3ad3c47d4a4f606ef6115a313.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 2]: /images/20211003/ccd9216db69b4b1eaceda9b4ff13d66c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 3]: /images/20211003/7e4b3884b6964341a69d8cae371b6e6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI3MTA4Ng_size_16_color_FFFFFF_t_70 4]: /images/20211003/aa29d60d27c045e6a52e158c2a927da8.png