LeetCode_滑动窗口_中等_220.存在重复元素III

àì夳堔傛蜴生んèń 2023-10-06 18:48 37阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 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

**提示：**  
0 <= nums.length <= 2 \* 104  
\-231 <= nums\[i\] <= 231 \- 1  
0 <= k <= 104  
0 <= t <= 231 \- 1

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/contains-duplicate-iii

## 2.思路 ##

（1）滑动窗口 & 有序集合（思路来自[LeetCode官方题解][LeetCode]）  
① 创建一个 treeSet，它是一个元素有序且不重复的集合；  
② 遍历数组 nums，先使用 **ceiling(Object e)** 函数返回 treeSet 中大于或等于 (long) nums\[i\] - (long) t 的最小元素，然后再判断 abs(nums\[i\] - nums\[j\]) <= t 是否成立，如果成立则直接返回 true，否则将当前元素 nums\[i\] 添加到 treeSet 中。此外为了保证滑动窗口的大小不超过 k，当 i ≥ k 时，将 nums\[i - k\] 移出 treeSet 即可；  
③ 若遍历能顺利完成，则说明不存在两个不同下标 i 和 j，使得 abs(nums\[i\] - nums\[j\]) <= t，同时又满足 abs(i - j) <= k，返回 false 即可。

相似题目：  
[LeetCode\_排序\_简单\_217.存在重复元素][LeetCode_217.]  
[LeetCode\_滑动窗口\_简单\_219.存在重复元素 II][LeetCode_219._ II]

## 3.代码实现（Java） ##

//思路1————滑动窗口 & 有序集合
    class Solution {
        
    	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        
    	    int length = nums.length;
    	    // treeSet: 元素有序且不重复的集合，此处使用长整型的目的是防止整数溢出
    	    TreeSet<Long> treeSet = new TreeSet<Long>();
    	    for (int i = 0; i < length; i++) {
        
    	        // ceiling(Object e): 返回 treeSet 中大于或等于 e 的最小元素，如果不存在则返回 null
    	        Long elem = treeSet.ceiling((long) nums[i] - (long) t);
    	        // (long) nums[i] - (long) t ≤ elem ≤ (long) nums[i] + (long) t 等价于 abs(nums[i] - nums[j]) <= t
    	        if (elem != null && elem <= (long) nums[i] + (long) t) {
        
    	            return true;
    	        }
    	        //将 nums[i] 加入到 treeSet 中
    	        treeSet.add((long) nums[i]);
    	        //保证滑动窗口的大小不超过 k
    	        if (i >= k) {
        
    	            treeSet.remove((long) nums[i - k]);
    	        }
    	    }
    	    return false;
    	}
    }

[LeetCode]: https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/
[LeetCode_217.]: https://blog.csdn.net/weixin_43004044/article/details/119303009
[LeetCode_219._ II]: https://blog.csdn.net/weixin_43004044/article/details/125702235