# 「力扣」第 220 题：存在重复元素 III（中等）
# 题目描述
给你一个整数数组 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
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
提示：
# 题意分析
题目让我们找出：在数组 nums[i] 中，在任意有效区间 [i..i + k] 里是否存在两个数的绝对值小于等于 t，存在则返回 true，不存在返回 false。存在性问题，找到符合题意的「数据对」即可返回 true，所有可能的情况都看完以后，都没有找到才返回 false。
# 方法一：暴力解法（超时）
枚举所有长度小于等于 k + 1 的「下标对」 （i, j），只要发现 nums[i] - nums[j] 的绝对值小于 t ，就返回 true。
参考代码 1：
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int len = nums.length;
if (len == 0 || k <= 0 || t < 0) {
return false;
}
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
// 注意：nums[j] - nums[i] 的结果可能会整型溢出，因此运算之前需要转换成 long 类型
if (Math.abs(j - i) <= k && Math.abs((long) nums[j] - (long) nums[i]) <= t) {
return true;
}
}
}
return false;
}
}
复杂度分析：
- 时间复杂度：
，这里数组的长度为 ，枚举可能的数对 ； - 空间复杂度：
。
优化的思路是：空间换时间，这里的空间还需要有比较大小的功能，比较容易想到的数据结构是二叉搜索树（方法二会说理由）。
# 方法二：滑动窗口 + 二叉搜索树
题目有两个不确定的因素：
- 两个不同位置下标的差的绝对值小于等于
； - 两个不同位置的数值的差的绝对值小于等于
。
暴力解法同时考虑了两个因素，在遍历数组的过程中没有记录下有用的信息。相比于两个不同位置的数值，下标的值是容易掌握的。于是我们可以 维护长度为 k + 1，但是真正数据结构里保存的元素个数可能是 k 也可能是 k + 1，取决于先插入新元素，还是先移除旧元素，这里不展开叙述了。）
我们把题目意思翻译一下：在数组 nums[i] 中，在任意长度大于等于 [i..i + k] 里是否存在两个数的绝对值小于等于 t，即
$$ |nums[i] - nums[j] | <= t $$
去掉绝对值符号
并且
可以把 nums[i] 看作新遍历到的元素，把 nums[j] 看作当前在滑动窗口中的元素。
根据（不等式 1）得：
$$ nums[i] - t \le nums[j] $$
根据（不等式 2）得：
$$ nums[i] + t \ge nums[j] $$
由此我们可以得到：如果在滑动窗口中能够找到一个元素
滑动窗口中可以有很多个元素的值满足「条件 1」，为了能够找同时满足两个条件的合适的
# 为什么使用二分搜索树
理由 1：由于维护的是固定长度的一系列数，除了最开始的几个数添加进数据结构以外。
- 当程序看到下标为
的元素的时候，就需要移除下标为 的元素； - 当程序看到下标为
的元素的时候，就需要移除下标为 的元素。
频繁的删除和添加元素，符合条件的数据结构是「查找表」，「查找表」的两种实现分别是「哈希表」和「二分搜索树（红黑树）」。
理由 2：根据上面的分析，我们需要找到
Java 的 ceiling(key) 函数提供了这样的功能：返回大于等于 key 的最小元素，如果不存在，返回空。下面的是这个函数的文档（通过 Intellij IDEA 查看）。
/**
* Returns the least key greater than or equal to the given key,
* or {@code null} if there is no such key.
*
* @param key the key
* @return the least key greater than or equal to {@code key},
* or {@code null} if there is no such key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map does not permit null keys
*/
K ceilingKey(K key);
参考代码 2：
import java.util.TreeSet;
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// 滑动窗口结合查找表，此时滑动窗口即为查找表本身（控制查找表的大小即可控制窗口大小）
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
// 边添加边查找，查找表中是否有大于等于 nums[i] - t 且小于等于 nums[i] + t 的值
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 (set.size() == k + 1) {
set.remove((long) nums[i - k]);
}
}
return false;
}
}
复杂度分析：
- 时间复杂度：
，遍历数组使用 ，在遍历的同时向二叉搜索树中插入元素和移除元素的时间复杂度是 ； - 空间复杂度：
。
另一种写法：在一开始就把滑动窗口左边的元素删除。
参考代码 3：
import java.util.TreeSet;
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int len = nums.length;
// 特判
if (len == 0 || k <= 0 || t < 0) {
return false;
}
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < len; i++) {
if (i > k) {
set.remove((long) nums[i - k - 1]);
}
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]);
}
return false;
}
}
复杂度分析：（同上）
作者：liweiwei1419 链接：https://suanfa8.com/binary-search-tree/solutions/0220-contains-duplicate-iii 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。