存在重复元素III

发表于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode每日一题，220. 存在重复元素 III

先看题目描述

c5E5QJ.png

算法和思路

滑动窗口 + 有序集合

我们可以维护一个大小为 k 的滑动窗口，每次遍历到元素 x 时，滑动窗口中包含元素 x 前面的最多 k 个元素，我们检查窗口中是否存在元素落在区间 [x - t，x + t] 中即可

为了快速判断出滑动窗口内是否存在符合条件的元素，我们可以使用有序集合来维护滑动窗口内的元素

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

算法源码

滑动窗口 + 有序集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> treeSet = new TreeSet<>();
        int n = nums.length;
        if (n < 2 || k == 0) {
            return false;
        }
        k = Math.min(n - 1, k);
        for (int i =  0; i < n; i++) {
            int num = nums[i];
            Long tar = treeSet.ceiling((long)num - t);
            if (tar != null && tar <= (long)num + t) {
                return true;
            }
            treeSet.add((long)num);
            if (i >= k) {
                treeSet.remove((long)nums[i - k]);
            }
        }
        return false;
    }
}

下面是自己一开始实现的滑动窗口 + 有序集合的方法的代码，实际上维护的是一个长度为 2k 的滑动窗口，运行效率较差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        int n = nums.length;
        if (n < 2 || k == 0) {
            return false;
        }
        k = Math.min(n - 1, k);
        for (int i =  0; i < n; i++) {
            if (i - k - 1 >= 0) {
                treeSet.remove(nums[i - k - 1]);
            }
            int num = nums[i];
            if (treeSet.contains(num)) {
                return true;
            }
            treeSet.add(num);
            Integer higher = treeSet.higher(num);
            Integer lower = treeSet.lower(num);
            if (higher != null && (long)higher - num <= t) {
                return true;
            }
            if (lower != null && (long)num - lower <= t) {
                return true;
            }
        }
        return false;
    }
}