题目描述

给定一个整数数组 ，找到数组中是否存在不同的 i 和 j，使得 i 和 j 的距离不超过 k，且 num[i] 和 num[j] 的差值不超过 t。

样例

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

算法

(multiset) $O(n \log k)$

1. 使用 C++ 提供的 multiset 来记录 [i-k, i-1] 中连续 k 个数字。
2. 对于当前的 num[i]，用 multiset 中的 lower_bound 找到 multiset 中第一个大于等于 num[i] - t 的数字。
3. 如果存在该数字 x，且 x <= nums[i] + t，则返回 true。

时间复杂度

• multiset 单个数字插入、删除、lower_bound 的时间复杂度都是 $O(\log k)$，故总时间复杂度为 $O(n \log k)$。

注意

• 此题需要 long long 类型，以防止 nums[i] + t 或 nums[i] - t 越界。

C++ 代码

#define LL long long
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<LL> hash;
        multiset<LL>::iterator it;
        for (int i = 0; i < nums.size(); i++) {
            it = hash.lower_bound((LL)(nums[i]) - t);
            if (it != hash.end() && *it <= (LL)(nums[i]) + t)
                return true;
            hash.insert(nums[i]);
            if (i >= k)
                hash.erase(hash.find(nums[i - k]));
        }
        return false;
    }
};