220. Contains Duplicate III

problem description

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.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

algorithm thought

这是这个系列的第三题，第二题加入了k表示只看前面k个数。第三题加入了t，代表数字的范围可以再t以内波动。

最开始，我想的是，还是和前一题一样处理，只不过判断是是否存在的时候，使用一个for循环判断这个范围内的值。但是这个题目的测试样例很bug，有个测试样例是INT_MAX，直接超时。

看了discuss，发现有人用桶的方法解这题，我感觉很巧妙。和之前桶排序一样。首先定下桶的大小，这里设为t+1。从INT_MIN开始，每个桶只能放一个数。如果出现相同的桶，那么就可以直接返回true，因为同一个桶中，最大的差值就是t。然后还需要在这个桶的前一个和后一个桶中找数，判断差值是否小于t。如果存在，返回true。通过这种办法，将数字换成桶，再重复利用上题的算法，这里时间复杂度可以到O(n)

code

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(k<1||t<0)
            return false;
        unordered_map<long,long> ma(k);
        long tmp=static_cast<long>(t);
        for(int i=0;i<nums.size();++i){
            long bucket_num=(static_cast<long>(nums[i])-INT_MIN)/(tmp+1);
            if(ma.count(bucket_num)||
              (ma.count(bucket_num+1)&&ma[bucket_num+1]-nums[i]<=t)||
              (ma.count(bucket_num-1)&&nums[i]-ma[bucket_num-1]<=t))
                return true;
            ma[bucket_num]=nums[i];
            if(i-k>=0){
                ma.erase((static_cast<long>(nums[i-k])-INT_MIN)/(tmp+1)); 
            }
        }
        return false;
    }
};

algorithm analysis

这里遍历一次数组得到结果，时间复杂度O(n)