ChunNote
0%

leetCode-220:Contains Duplicate III

发表于 分类于

问题描述

给定一个整数二维数组，以及整数 k 和 t，要求判断数组中是否存在两个元素下标 i 和 j，使得 abs(i - j) <= k 并且 abs(nums[i] - nums[j]) <= t，如果存在则返回 true, 否则返回 false。题目链接：**点我**

样例输入输出

输入：nums = [1,2,3,1], k = 3, t = 0

输出：true

输入：nums = [1,5,9,1,5,9], k = 2, t = 3

输出：false

问题解法

用一个容量为 k 的 TreeSet 来存储数组的元素，遍历数组元素，对于每个元素，判断 TreeSet 中是否存在 [num - t, num + t] 中的元素，如果存在，则说明存在重复元素，否则不存在重复元素。为了快速判断 [num - t, num + t] 区间的元素是否在 TreeSet 中，可以使用 ceiling 函数获取 num - t 的值，然后与 num + t 进行比较。需要额外注意的时，运算过程中需要用 long 类型，否则两个数字相加可能超出范围。代码如下

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

            treeSet.add((long) nums[i]);
            if (i >= k)
            {
                treeSet.remove((long) nums[i - k]);
            }
        }

        return false;
    }
}

参考资料

https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode-bbkt/