220. Contains Duplicate III

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= 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
 

Constraints:

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

这题说简单也简单，说难也难。简单的是，可以暴力破解。难的是，暴力破解的时间复杂度不符合题意。

暴力破解很简单，就是遍历k个数字，看看k个数字内是否有符合条件的数值。但是当k很大的时候，这个复杂度有点高。能不能做下优化来解决这个呢？

我们可以把k个数字存入set中。set的底层数据结构是红黑树，本身就是有序的，所以我们可以通过迭代器有序的遍历其中的值。

当我们遍历一个值的时候，首先判断是否插入成功，加入失败，说明这个数字存在过了，那么肯定是符合条件的。假如失败，则可以获取插入的值的迭代器，通过此迭代器可以访问它前后的数值，看看是否满足题意。

这题我错了很多次，但是也学习到了不少的思想，还是挺值得的，毕竟试错的经验是通往提升途径中必须得经历的。

class ContainsDuplicateIII : public Solution {
public:
    void Exec() {
        
    }
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<int> window;
        for (int i = 0; i < nums.size(); i++) {
            if (window.size() > k) {
                window.erase(nums[i - k - 1]);
            }
            auto ires = window.insert(nums[i]);
            if (!ires.second) return true;
            auto it = ires.first;
            if (it != window.begin()) {
                auto prev = it;
                prev--;
                if (abs(int64_t(*prev) - int64_t(nums[i])) <= t) return true;
            }
            if (++it != window.end() && abs(int64_t(*it) - int64_t(nums[i])) <= t) {
                return true;
            }
        }
        return false;
    }
};