LeetCode题练习与总结：存在重复元素Ⅲ--220

一、题目描述

给你一个整数数组 nums 和两个整数 indexDiff 和 valueDiff 。

找出满足下述条件的下标对 (i, j)：

i != j,
abs(i - j) <= indexDiff
abs(nums[i] - nums[j]) <= valueDiff

如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
输出：true
解释：可以找出 (i, j) = (0, 3) 。
满足下述 3 个条件：
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

示例 2：

输入：nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
输出：false
解释：尝试所有可能的下标对 (i, j) ，均无法满足这 3 个条件，因此返回 false 。

提示：

2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10^9

二、解题思路

遍历数组 nums，对于每个元素 nums[i]，在它的后面寻找满足条件的元素 nums[j]。
使用一个大小为 indexDiff + 1 的滑动窗口来维护可能满足条件的元素。
在滑动窗口中，使用一个有序的数据结构（如TreeSet）来维护窗口内的元素，这样可以通过二分查找来快速判断是否存在满足条件的元素。
对于每个元素 nums[i]，在有序集合中查找大于等于 nums[i] - valueDiff 且小于等于 nums[i] + valueDiff 的元素。
如果找到了满足条件的元素，则返回 true。
如果遍历完数组都没有找到满足条件的元素对，则返回 false。

三、具体代码

import java.util.TreeSet;class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {TreeSet<Long> window = new TreeSet<>();for (int i = 0; i < nums.length; i++) {// 移除窗口外的元素if (i > indexDiff) {window.remove((long) nums[i - indexDiff - 1]);}// 查找是否存在满足条件的元素Long ceiling = window.ceiling((long) nums[i] - valueDiff);if (ceiling != null && ceiling - nums[i] <= valueDiff) {return true;}// 将当前元素添加到窗口中window.add((long) nums[i]);}return false;}
}

在这段代码中，我们使用 TreeSet 来维护一个大小为 indexDiff + 1 的滑动窗口。在每次迭代中，我们首先移除窗口外的元素，然后查找窗口内是否存在满足条件的元素。如果找到了，则返回 true。如果没有找到，我们将当前元素添加到窗口中，并继续下一次迭代。如果遍历完数组都没有找到满足条件的元素对，则返回 false。

四、时间复杂度和空间复杂度

1. 时间复杂度

对于数组 nums 中的每个元素，我们最多执行以下操作一次：
- 移除窗口外的元素：这是 TreeSet 的 remove 操作，其时间复杂度为 O(log k)，其中 k 是 TreeSet 的大小，在本例中 k 等于 indexDiff + 1。
- 查找是否存在满足条件的元素：这是 TreeSet 的 ceiling 操作，其时间复杂度也是 O(log k)。
- 将当前元素添加到窗口中：这是 TreeSet 的 add 操作，其时间复杂度为 O(log k)。
由于数组 nums 的长度为 n，因此上述每个操作总共执行 n 次。

综上所述，总的时间复杂度为 O(n * log k)，其中 k 是滑动窗口的大小，即 indexDiff + 1。由于 k 是一个常数，因此我们可以将其视为 O(log n)，所以总的时间复杂度可以简化为 O(n * log n)。

2. 空间复杂度

我们使用了一个 TreeSet 来维护滑动窗口中的元素，其大小最多为 indexDiff + 1。
因此，空间复杂度主要取决于 TreeSet 的大小，为 O(k)，其中 k 是 indexDiff + 1。

由于 indexDiff 是一个给定的常数，因此空间复杂度可以简化为 O(1)，即常数空间复杂度。

五、总结知识点

类定义：
- class Solution：定义了一个名为 Solution 的类。
方法定义：
- public boolean containsNearbyAlmostDuplicate(...) {...}：定义了一个公共方法 containsNearbyAlmostDuplicate，它返回一个布尔值。
数据结构：
- TreeSet<Long>：使用 TreeSet 来存储一个有序集合，它基于红黑树实现，可以保持元素的排序状态。
基本类型与包装类型：
- int[] nums：使用基本类型 int 的数组来存储输入的整数序列。
- Long：在 TreeSet 中使用包装类型 Long 而不是基本类型 long，因为 TreeSet 不支持基本类型。
循环结构：
- for (int i = 0; i < nums.length; i++) {...}：使用 for 循环来遍历数组 nums。
条件语句：
- if (i > indexDiff) {...}：使用 if 语句来检查是否需要移除窗口外的元素。
集合操作：
- window.remove(...)：从 TreeSet 中移除一个元素。
- window.ceiling(...)：在 TreeSet 中查找大于等于给定值的最小元素（即天花板）。
- window.add(...)：向 TreeSet 中添加一个元素。
类型转换：
- (long) nums[i]：将 int 类型的数组元素转换为 long 类型，以避免在比较时可能出现的整数溢出。
逻辑运算：
- ceiling != null && ceiling - nums[i] <= valueDiff：使用逻辑与运算符来检查是否找到满足条件的元素。
方法返回：
- return true：当找到满足条件的元素对时，提前返回 true。
- return false：如果没有找到满足条件的元素对，在遍历结束后返回 false。
数学运算：
- ceiling - nums[i]：进行减法运算以检查两个元素的差值是否在允许的范围内。