欢迎访问LeetCode题解合集

题目描述

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值小于等于 t ，且满足 i 和 j 的差的绝对值也小于等于 k 。

如果存在则返回 true，不存在返回 false。

示例 1:

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

示例 2:

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

示例 3:

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

题解：

使用 map<long,int> 保存每个元素和它的位置。

从左往右遍历 nums ，对于每个元素 nums[i] ，利用 lower_bound 查找第一个大于等于 nums[i] - t 的位置，利用 upper_bound 查找第一个大于 nums[i] + t 的位置，然后枚举两个位置，判断是否有满足下标差距不大于 k 的元素。

时间复杂度：$O(n^2)$

额外空间复杂度：$O(n)$

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        map<long, int> hash;
        for ( int i = 0; i < nums.size(); ++i ) {
            auto l = hash.lower_bound((long)nums[i] - t);
            auto r = hash.upper_bound((long)nums[i] + t);
            for ( auto it = l; it != r; ++it ) {
                if ( i - it->second <= k ) return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};
/*
时间：44ms，击败：56.61%
内存：14.7MB，击败：59.19%
*/

第二重循环可以优化掉，只维护大小为 k 的窗口，在窗口内一定满足下标差值不超过 k ，省掉下标判断。

时间复杂度：$O(nlogk)$

额外空间复杂度：$O(n)$

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if ( !k ) return false;
        map<long, int> hash;
        for ( int i = 0; i < nums.size(); ++i ) {
            auto l = hash.lower_bound((long)nums[i] - t);
            if ( l != hash.end() && l->first <= (long)nums[i] + t )
                return true;
            if ( hash.size() == k )
                hash.erase( nums[i - k] );
            hash[nums[i]] = i;
        }
        return false;
    }
};
/*
时间：36ms，击败：81.37%
内存：14.8MB，击败：43.66%
*/

因为涉及到 erase 操作，速度提升不明显。

由于我们维护了大小为 k 的窗口，所以没必要保存下标，使用 set 保存值即可。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if ( !k ) return false;
        set<long> hash;
        for ( int i = 0; i < nums.size(); ++i ) {
            auto l = hash.lower_bound((long)nums[i] - t);
            if ( l != hash.end() && *l <= (long)nums[i] + t )
                return true;
            if ( hash.size() == k )
                hash.erase( nums[i - k] );
            hash.insert(nums[i]);
        }
        return false;
    }
};
/*
时间：36ms，击败：81.37%
内存：14.6MB，击败：72.67%
*/