大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个整数数组和一个整数k和t，判断数组中是否存在两个不同下标的索引使得abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k，存在返回true。”
2、题目描述
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(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
二、解题
1、思路分析
题意要判断整数数组中，是否存在 满足 abs(nums[i] - nums[j]) <= t，同时又满足 abs(i - j) <= k的可能。
根据题意，对于任意一个位置i，如果在下标范围[max(0,i-k),i]，值的范围在[i-t,i+t]的数，那么就是我们要求得数。
注意到两个相邻的元素，各自的左侧的k个元素中有k-1个是重合的。
可以使用滑动窗口的思路，维护一个大小为k的滑动窗口，每次遍历元素x的时候，检查窗口中是否存在元素落在[x-t,x+t]中即可。
但是，每次遍历到位置i，往后检查k个元素，这样做的时间复杂度为O(nk)，会超时。
需要一个有序集合的数据结构去优化这个过程，该数据结构去维护长度为k的滑动窗口的数，然后可以高效的查询、插入、删除等操作。
2、代码实现
代码参考：
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { int n = nums.length; TreeSet<Long> set = new TreeSet<Long>(); for (int i = 0; i < n; i++) { Long ceiling = set.ceiling((long) nums[i] - (long) t); if (ceiling != null && ceiling <= (long) nums[i] + (long) t) { return true; } set.add((long) nums[i]); if (i >= k) { set.remove((long) nums[i - k]); } } return false; } }
3、时间复杂度
时间复杂度：O(o log(min(n,k)))
其中n是数组的长度，每个元素至多被插入到有序集合和从有序集合中删除一次。
空间复杂度：O(min(n,k))
其中n是给定数组的长度，有序集合中至多包含min(n,k+1)个元素。
三、总结
有序集合中查找大于等于x-t的最小的元素y，如果y存在，且y≤x+t，就找到了一堆符合条件的元素。
完成检查后，将x插入到有序集合汇总。
如果有序集合中元素怒数量超过了k，则将有序集合中最早被插入的元素删除即可。
