C++ 算法：判断数组中是否存在距离小于 k 且差值小于 t 的两个元素

class Solution {
public:
    // 获取元素所属的桶的编号
    int getID(int x, long w) {
        return x < 0 ? (x + 1ll) / w - 1 : x / w;
    }

    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        unordered_map<int, int> mp; // 用于存储桶的编号和对应的元素值

        int n = nums.size();
        for (int i = 0; i < n; i++) {
            long x = nums[i];
            int id = getID(x, t + 1ll); // 获取元素所属的桶的编号

            // 检查当前桶是否存在元素，如果存在则返回 true
            if (mp.count(id)) {
                return true;
            }

            // 检查相邻桶是否存在元素满足条件，如果存在则返回 true
            if (mp.count(id - 1) && abs(x - mp[id - 1]) <= t) {
                return true;
            }
            if (mp.count(id + 1) && abs(x - mp[id + 1]) <= t) {
                return true;
            }

            mp[id] = x; // 将元素存入对应的桶中

            if (i >= k) {
                mp.erase(getID(nums[i - k], t + 1ll)); // 移除窗口范围之外的桶
            }
        }

        return false;
    }
};

这段代码使用了桶排序的思想，在划分桶的过程中，利用 getID() 函数计算元素所属的桶的编号。然后，使用 unordered_map mp 来存储桶的编号和对应的元素值。

具体步骤如下：

1. 定义 getID() 函数，用于计算元素所属的桶的编号。
2. 创建一个 unordered_map mp，用于存储桶的编号和对应的元素值。
3. 遍历数组 nums，对于每个元素 x：
   • 计算 x 所属的桶的编号 id。
   • 检查当前桶是否存在元素，如果存在则返回 true。
   • 检查相邻桶是否存在元素满足条件，如果存在则返回 true。
   • 将元素 x 存入桶中，并更新 mp。
   • 如果窗口大小超过 k，移除窗口范围之外的桶。
4. 如果遍历完所有元素仍未找到满足条件的元素对，返回 false。

这个算法的时间复杂度为 O(n)，其中 n 是数组的长度。由于使用了桶排序的思想，所以在给定的条件下，这个算法的时间复杂度是最低的。