LeetCode220-存在重复元素III

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/contains-duplicate-iii/

中文链接：https://leetcode-cn.com/problems/contains-duplicate-iii/

题目详述

给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。

示例 1:

1
2
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true

示例 2:

1
2
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true

示例 3:

1
2
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false

题目详解

本题是 LeetCode219-存在重复元素II 的升级版，解题思路是类似的。

方法一：

  • 遍历数组，维持一个大小不超过 k 的窗口。对于当前元素 num，判断窗口中是否存在属于区间 [num - t, num + t] 的元素。若存在，说明满足条件，返回 true 即可。
  • 为了便于在窗口内查找，运用 TreeSet 来构建这个窗口是比较合适的。
  • 时间复杂度为 O(nlogk)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00220 {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            Long cur = set.ceiling((long) nums[i] - t);
            if (cur != null && cur <= (long) nums[i] + t) {
                return true;
            }
            set.add((long) nums[i]);
            if (set.size() > k) {
                set.remove((long) nums[i - k]);
            }
        }
        return false;
    }
}

方法二：

  • 运用桶排序的思想来解决本题。
  • 构建桶，桶的大小为 1L + t，桶内元素差值必然不超过 t。也就是说同一桶内的元素必然满足条件。
  • 若两个元素不属于同一个桶，相邻桶之间存在满足条件的可能，不相邻的桶之间的两个元素最小间隔大于桶的大小，必然不满足条件。
  • 遍历数组，得到当前元素所属的桶 id，若这个桶内存在元素，说明满足条件。否则判断与它相邻的两个桶是否满足条件。
  • 注意，本题有很多边界条件，比如转为 long 型计算防止溢出；两个不同的索引 i 和 j 说明 k >= 1；t 是绝对值说明 t >= 0。
  • 时间复杂度为 O(n)。
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
30
31
32
public class LeetCode_00220 {

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) {
            return false;
        }
        // 桶的大小 1L + t，桶内元素差值必然不超过 t
        long w = 1L + t;
        // 构建桶
        Map<Long, Long> bucket = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            // 得到桶 id
            long id = getId(nums[i], w);
            if (bucket.containsKey(id) ||   // 同一个桶的元素差值必然不超过 t
                    bucket.containsKey(id - 1) && nums[i] - bucket.get(id - 1) <= t ||  // 前面一个桶二者差值不超过 t
                    bucket.containsKey(id + 1) && bucket.get(id + 1) - nums[i] <= t) {  // 后面一个桶二者差值不超过 t
                return true;
            }
            // 维持窗口大小不超过 k
            if (bucket.size() == k) {
                bucket.remove(getId(nums[i - k], w));
            }
            bucket.put(id, Long.valueOf(nums[i]));
        }
        return false;
    }

    private long getId(long num, long w) {
        // num 可能为负数，减去 Integer.MIN_VALUE 这个偏移量得到非负数
        return (num - Integer.MIN_VALUE) / w;
    }
}