LeetCode 220 Contain Duplicate III

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

Diffculty
Medium

Similar Problems

[LeetCode 217] Contain Duplicates Easy [LeetCode 219] Contain Duplicates II Easy

Analysis

利用multiset进行BST的二分搜索。lower_bound()返回一个迭代器，指向大于等于输入值的第一个元素。 从左到右扫描数组，若multiset的元素数量等于k+1，则删去最先进入的元素。由于multiset.size()始终小于等于k+1， 所以下标之差是肯定小于等于k的。然后利用lower_bound()，找到第一个大于等于nums[i]-t的元素，若该元素和nums[i]的差的绝对值小于等于t，则返回真。

注意：为了防止溢出，必须将数据转化为long long进行处理！

Solutions

解法一

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        multiset<long long> bst;
        for (int i = 0; i < nums.size(); ++i) {
            if (bst.size() == k + 1) bst.erase(bst.find(nums[i - k - 1]));
            auto lb = bst.lower_bound(nums[i]);
            if (lb != bst.end() && abs(*lb - nums[i]) <= t) return true;
            auto ub = bst.upper_bound(nums[i]);
            if (ub != bst.begin() && abs(*(--ub) - nums[i]) <= t) return true;
            bst.insert(nums[i]);
        }
        return false;
    }
};

解法二 直接找nums[i] - t的lower_bound, 这个值就是与nums[i]差值最近的值。

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

Reference