☆打卡算法☆LeetCode 220. 存在重复元素 III 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定一个整数数组和一个整数k和t，判断数组中是否存在两个不同下标的索引使得abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k，存在返回true。”

题目链接：

来源：力扣（LeetCode）

链接： 220. 存在重复元素 III - 力扣（LeetCode）

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 &amp;&amp; ceiling <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }
}

image.png

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，则将有序集合中最早被插入的元素删除即可。