Use HashSet to attempt to meet the requirements in the window⌗ 

class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		auto left = 0;
		auto K = 0;
		set<long> hset; // set in cpp is an sorted set
		for (auto right = 0; right < nums.size(); right++) {
			K = right - left;
			if (K > k) {
				hset.erase(nums[left]);
				left++;
			}
			hset.insert(nums[right]);

			// some numbers are the same.
			if (hset.size() < (right - left + 1)) {
				return true;
			}

			// abs less than or equal t
			auto prev = hset.begin();
			for (auto iter = hset.begin(); iter != hset.end(); iter++) {
				if (iter != prev && abs(*prev - *iter) <= t) {
					return true;
				}
				prev = iter;
			}

		}
		return false;
	}
};


// 1. find previous value that meet the requirement, which is abs(nums[i] - nums[j]) <= t
// 2. See if also meet the requirement, which is abs(i - j) <= k, otherwise slide left
//
// Use a fixed window, which size is ~k~. And maintain a set of numbers in the window.
// To check if there numbers meet the requirement.

It’s too slow and got “Time Limit Exceeded”: https://leetcode.com/submissions/detail/658425251/testcase/. In this case the t is 0, so we can avoid the embed for loop with a if condition:

if (t != 0 ) {
	// abs less than or equal t
	auto prev = hset.begin();
	for (auto iter = hset.begin(); iter != hset.end(); iter++) {
		if (iter != prev && abs(*prev - *iter) <= t) {
			return true;
		}
		prev = iter;
	}
}

But then we got: https://leetcode.com/submissions/detail/658426815/testcase/.

Use SortedSet lower_bound/uppoer_bound to meet the requirements of abs(nums[i] - nums[j]) < t⌗

After a search of OrderedSet. As we known nums[j] and t, we need find which range of nums[i] is meeting the requirement. Then we can find it in the OrderedSet.

class Solution {
public:
	bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
		auto left = 0;
		auto K = 0;
		set<long> hset; // set in cpp is an sorted set
		for (auto right = 0; right < nums.size(); right++) {
			long n = nums[right];
			if ((right - left) > k) {
				hset.erase(nums[left++]);
			}
			// Find a value that equal or greater than required.
			// According to abs(nums[i] - nums[j]) <= t, the differ between
			// nums[i] and nums[j] less than t.
			// Which means nums[i] - nums[j] <= t and nums[j] - nums[i] <= t.
			// So here, we find back /t/ based on current value, as we are using
			// sorted set, so a bigger value could be found too.
			// For example, now the value is 5, t is 2. Then we found the value
			// greater than or equal to 3, the possible values may found: 3, 4, 5, 6, 7.
			// Any of them is meeting the requirements.
			auto iter = hset.lower_bound(n - t);
			if (iter != hset.end() and (*iter - n) <= t) {
				return true;
			}
			hset.insert(nums[right]);
		}
		return false;
	}
};