Leetcode-220-存在重复元素III

Leetcode-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

提示：

0 <= nums.length <= 2 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^4
0 <= t <= 2^31 - 1

算法思路：滑动窗口

• 对于序列中每一个元素 x 左侧的至多 k 个元素，如果这 k 个元素中存在一个元素落在区间[x - t, x + t]中，我们就找到了一对符合条件的元素。
• 注意到对于两个相邻的元素，它们各自的左侧的 k 个元素中有 k−1 个是重合的。
  • 于是我们可以使用滑动窗口的思路，维护一个大小为 k 的滑动窗口
  • 每次遍历到元素 x 时，滑动窗口中包含元素 x 前面的最多 k 个元素
  • 检查窗口中是否存在一个元素落在区间[x - t, x + t]中，我们就找到了一对符合条件的元素。

注意：

• 如果使用队列维护滑动窗口内的元素，由于元素是无序的，我们只能对于每个元素都遍历一次队列来检查是否有元素符合条件。

  • 如果数组的长度为 n，则使用队列的时间复杂度为 O(nk)，会超出时间限制。
  • 因此我们希望能够找到一个数据结构维护滑动窗口内的元素，该数据结构需要满足以下操作：
    • 支持添加和删除指定元素的操作，否则我们无法维护滑动窗口；
    • 内部元素有序，支持二分查找的操作，这样我们可以快速判断滑动窗口中是否存在元素满足条件
    • 具体而言，对于元素 x，当我们希望判断滑动窗口中是否存在某个数 y 落在区间[x - t, x + t]中，只需要判断滑动窗口中所有大于等于x - t的元素中的最小元素是否小于等于x + t即可。

具体实现：

• 实现方面，我们在有序集合中查找大于等于 x - t的最小的元素y，如果 y 存在，且 y ≤ x+t，我们就找到了一对符合条件的元素。

• 完成检查后，我们将 x 插入到有序集合中，如果有序集合中元素数量超过了 k，我们将有序集合中最早被插入的元素删除即可。

• 如果当前有序集合中存在相同元素，那么此时程序将直接返回true。因此本题中的有序集合无需处理相同元素的情况。

• 为防止整型 int 溢出，我们既可以使用长整型 long，也可以对查找区间[x - t, x + t]进行限制，使其落在 int 范围内。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // 1. 使用有序集合来维护大小为k的滑动窗口
        int n = nums.length;
        TreeSet<Long> set = new TreeSet<Long>();                            // long为了防止溢出

        // 2. 处理逻辑：遍历每个元素，滑动窗口包含了nums[i]的前k个元素，检查是否落在了[nums[i] - t,nums[i] + t]的区间内
        for (int i = 0; i < n; i++) {
            // 2.1 判断有序集合中是否存在符合条件的元素
            Long ceiling = set.ceiling((long) nums[i] - (long) t);          // ceiling()：方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回null.
            if (ceiling != null && ceiling <= (long) nums[i] + (long) t) {  // 存在这样一对元素就直接返回
                return true;
            }

            // 2.2 不存在的话暂时添加到有序集合中
            set.add((long) nums[i]);

            // 2.3 维护大小为k的滑动窗口，删除超出范围的最早的元素
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        // 3. 都不满足返回false
        return false;
    }
}

复杂度分析

• 时间复杂度：O(nlog(min(n,k))) , n 是遍历一遍数组，log(min(n,k)) 是对集合的插入和删除操作
• 空间复杂度：O((min(n,k))) , 使用大小为k的滑动窗口，最差情况下是数组的大小

打赏