leetcode 220. Contains Duplicate III | 220. 存在重复元素 III （Treeset解法+分桶解法）

女爷i 2022-10-07 09:59 104阅读 0赞

## 题目 ##

[https://leetcode.com/problems/contains-duplicate-iii/][https_leetcode.com_problems_contains-duplicate-iii]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：Treeset 解法，滑动窗口 & 二分 ####

思路参考：[https://leetcode-cn.com/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/][https_leetcode-cn.com_problems_contains-duplicate-iii_solution_gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv]

用 Treeset 维护滑动窗口。Treeset 基于红黑树，插入和查找都有折半的效率。

import java.util.Arrays;
    import java.util.TreeSet;
    
    class Solution { 
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { 
            TreeSet<Long> set = new TreeSet<>();
            for (int i = 0; i < nums.length; i++) { 
                Long floor = set.floor((long) nums[i]); // 小于的里面的最大的
                if (floor != null && floor >= (long) nums[i] - t) return true;
    
                Long ceiling = set.ceiling((long) nums[i]); // 大于的里面的最小的
                if (ceiling != null && ceiling <= (long) nums[i] + t) return true;
    
                set.add((long) nums[i]);
                if (i - k >= 0) set.remove((long) nums[i - k]);
            }
            return false;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

### 方法2：分桶解法 ###

参考：[https://leetcode-cn.com/problems/contains-duplicate-iii/solution/c-li-yong-tong-fen-zu-xiang-xi-jie-shi-b-ofj6/][https_leetcode-cn.com_problems_contains-duplicate-iii_solution_c-li-yong-tong-fen-zu-xiang-xi-jie-shi-b-ofj6]

将 t+1 作为桶的模：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]

#### 核心思路 ####

我们从头开始遍历数组，对于当前下标i，有效的桶是下标为\[i-k,i+k\]的元素构造的桶，对于每一个i我们只需要看前面是否有无效的桶并删除即可，后面的元素我们没遍历到，自然也不会产生桶，所以 \[i-k，i\] 的桶是有效的，如果 nums\[i-(k+1)\] 产生的桶存在，我们要把其删除掉。因为 abs(i-(i-(k+1))) = abs(k+1) = k+1 > k。这是不在我们下标范围内的元素产生的桶，我们不需要判断是否满足条件，直接把这个桶删除了。

对于遍历到的元素 nums\[i\] 进行分桶，获取当前桶 ID，如果当前桶中已经有元素了，那么说明能找到符合条件的元素，直接返回true（因此，我们每个桶中最多只可能有一个元素，多了我们会直接返回结果）。如果当前桶没有元素，那么看看前相邻的桶有没有元素，如果有元素，那么进行做差比较，判断是否满足条件，满足则返回true。如果没有找到，那么把这个元素装入桶中，供别的元素判断。如果到最后都没有找到满足条件的元素，我们就返回false;

class Solution { 
    public:
        long getID(long x, long t){ 
            //如果x元素大于等于零,直接分桶
            if(x>=0){ 
                return x / ( t + 1 );
            }else{ 
            //如果x元素小于零,偏移后再分桶
                return ( x + 1 )/( t + 1 ) - 1 ;
            }
            return 0;
        }
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { 
            int n = nums.size();
            //我们用unordered_map来实现桶,其底层实现是一个哈希表.
            unordered_map<int,int> m;
            for(int i = 0 ; i < n; i++ ){ 
                //当前元素
                long  x = nums[i];
                //给当前元素生成id,这里我们同一个id的桶内元素满足abs(nums[i] - nums[j]) <= t
                int id = getID(x,t);
                //前面的i-(k+1)是超出了范围的桶,我们把它提前删除,以免影响判断
                if( i-(k+1) >= 0 ){ 
                    //把下标不满足我们判断范围的桶删除了
                    m.erase(getID(nums[i-(k+1)],t));
                }
                //看看当前元素属于的桶中有没有元素
                if(m.find(id)!=m.end()){ 
                    return true;
                }
                //看看前面相邻桶有没有符合条件的
                if(m.find(id - 1) != m.end() && abs(m[id-1]-x) <= t){ 
                    return true;
                }
                //看看后面相邻桶有没有符合条件的
                if(m.find(id + 1) != m.end() && abs(m[id+1]-x) <= t){ 
                    return true;
                }
                //分桶,把这个元素放入其属于的桶
                m[id] = x;
            }
            return false;
        }
    };

#### Q&A ####

##### 1、每个桶只存放一个元素，够用吗？ #####

桶的解法相当凝练，不过有一点可以啰嗦两句。不知道有没有人疑惑，在比较id - 1和id + 1这两个相邻桶时，只比较了一个元素，这足够吗？哈希表的行为不是会用新元素覆盖旧元素，一个桶里有多个元素怎么办？

其实是覆盖根本不会发生…因为一旦要覆盖，就说明存在两个元素同属一个桶，直接返回true了。这就是题解说的“一个桶内至多只会有一个元素”——数组输入里当然可以有多个元素属于同一个桶，但是一旦出现一对，算法就结束了。

##### 2、 i-(k+1) 是超出了范围的桶，我们把它提前删除的话，会不会误伤有效范围内的桶？ #####

误伤根本不会发生。假设有一个序列是 `5, 7, 9, 1_a, [3, 5, 1_b, 1_c]` 的话（括号内是当前窗口），我们会担心删除 1\_a 的时候会误伤 1\_b 的桶。而实际上，不会存在这种误伤问题。因为只有相同桶里的元素才能被误伤，而既然有两个元素属于同一个桶，算法早就应该结束了。

[https_leetcode.com_problems_contains-duplicate-iii]: https://leetcode.com/problems/contains-duplicate-iii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/c0f3df4709914b27996095fa793420a0.png
[https_leetcode-cn.com_problems_contains-duplicate-iii_solution_gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv]: https://leetcode-cn.com/problems/contains-duplicate-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-hua-d-dlnv/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70]: /images/20221005/fb0d2c14d4374ae0ab1d7ed7713396f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/0b674cf157b64d87a45d2f96173232a2.png
[https_leetcode-cn.com_problems_contains-duplicate-iii_solution_c-li-yong-tong-fen-zu-xiang-xi-jie-shi-b-ofj6]: https://leetcode-cn.com/problems/contains-duplicate-iii/solution/c-li-yong-tong-fen-zu-xiang-xi-jie-shi-b-ofj6/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_1_color_FFFFFF_t_70 1]: /images/20221005/bae7e32e06af4ade93d99a3920fb8d08.png