leetcode 220. Contains Duplicate III TreeSet和SortedSet的应用 + C++的lower_bound的应用 + 移动窗口

亦凉 2022-06-08 10:16 145阅读 0赞

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums\[i\] and nums\[j\] is at most t and the absolute difference between i and j is at most k.

这道题题意很简单明了，但是我暂时想不清楚怎么做，我在网上看到有人使用SortSet和TreeSet，真的很棒，但是之前没用过，所以还待学习。

建议和这一道题[leetcode 217. Contains Duplicate 遍历 + HashSet][leetcode 217. Contains Duplicate _ _ HashSet] 和 这一道题[leetcode 219. Contains Duplicate II 学习HashMap][leetcode 219. Contains Duplicate II _HashMap] 一起学习。

**C++中的lower\_bound和upper\_bound的意思其实很简单，就两句话：**  
**lower\_bound(key):返回map中第一个大于或等于key的迭代器指针**  
**upper\_bound(key):返回map中第一个大于key的迭代器指针**

代码如下：

import java.util.SortedSet;
    import java.util.TreeSet;
    
    public class Solution 
    {  
        /*
         * http://blog.csdn.net/xudli/article/details/46323247
         * 
         * 这个方法是使用Java中的Sortset结构，set保存的始终是jindex在k之内，值相差在t之内的元素，
         * 一旦不为空就表示存在元素
         * index只差不超过k，值不超过t
         * */
        public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) 
        {  
            //input check  
            if(k<1 || t<0 || nums==null || nums.length<2) 
                return false;  
    
            SortedSet<Long> set = new TreeSet<Long>();  
            for(int j=0; j<nums.length; j++) 
            {  
                SortedSet<Long> subSet =  set.subSet((long)nums[j]-t, (long)nums[j]+t+1);  
                if(!subSet.isEmpty()) 
                    return true;  
                //滑动窗口
                if(j>=k)
                    set.remove((long)nums[j-k]);   
                set.add((long)nums[j]);  
            }  
            return false;  
        }  
    
        /*
         * TreeSet数据结构（Java）使用红黑树实现，是平衡二叉树的一种。
         * 该数据结构支持如下操作：
         * 1. floor()方法返set中≤给定元素的最大元素；如果不存在这样的元素，则返回 null。
         * 2. ceiling()方法返回set中≥给定元素的最小元素；如果不存在这样的元素，则返回 null。
         * 
         * index只差不超过k，值不超过t
         * 
         * */
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) 
        { 
            if(k<1||t<0) 
                return false; 
            TreeSet<Integer> set = new TreeSet<Integer>();
            for(int i=0;i<nums.length;i++)
            {
                int n = nums[i];
                if((set.floor(n)!=null&& n<=t+set.floor(n))
                    ||(set.ceiling(n)!=null && set.ceiling(n)<=t+n))
                    return true;
    
                set.add(n);  
              //滑动窗口
                if(i>=k)
                    set.remove(nums[i-k]);
            }
            return false;      
        }
    }

下面是C++的做法，就是使用一个下届函数来做判定

**需要注意的是：这里可能出现int越界的现象，所以注意使用long等等数据结构**

代码如下：

#include <iostream>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
        {
            if (k < 1 || t < 0 || nums.size() <= 0)
                return false;
            set<long> s;
            for (int i = 0; i < nums.size(); i++)
            {
                auto pos = s.lower_bound(((long)nums[i] - t));
                if (pos != s.end() && *pos <= (long)nums[i] + t)
                    return true;
                if (i >= k)
                    s.erase(s.find(nums[i-k]));
                s.insert(nums[i]);
            }
            return false;
    
        }
    };

[leetcode 217. Contains Duplicate _ _ HashSet]: http://blog.csdn.net/jackzhang_123/article/details/78059836
[leetcode 219. Contains Duplicate II _HashMap]: http://blog.csdn.net/jackzhang_123/article/details/78060441