CloudLander's Blog
0%

220. Contains Duplicate III

发表于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Medium

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

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

笨办法就是双重循环，如果下标绝对值符合后再看数值是否符合，会超时

网上找的中文解释都没看懂。

使用TreeSet数据结构，可以借助TreeSet中有用的函数

TreeSet.floor(x) 表示TreeSet中小于或等于x的最大元素
TreeSet.ceiling(x) 表示TreeSet中大于或等于x的最小元素

对于数组中任意一个数nums[i], 与其绝对值差小于等于为t的区间为 [nums[i]-t，nums[i]+t], 数轴表示如下

    I__________I__________I
nums[i]-t   nums[i]      nums[i]+t

使用TreeSet的floor和ceiling函数，可以得到是否有数字在上述区间内
即：f = floor(nums[i] + t) 且 f>=nums[i]，说明f在[ nums[i], nums[i]+t]内
c = ceiling(nums[i] - t) 且 c<=nums[i]，说明c在[ nums[i]-t, nums[i]]内

如果存在f或者c，然后要保证的是 它们的索引和i差距小于k，则只需维持TreeSet中始终只保留窗口大小为k的元素即可（在访问nums[i]时，TreeSet中始终只保留nums[i-k]到nums[i-1] ）。

这样，只要存在f或者c，就存在满足条件的值，因为TreeSet中元素的坐标都满足和i的约束关系，直接返回。
若不存在，则把nums[i]加入TreeSet，删去nums[i-k]（因为下一个要访问的是nums[i+1]，nums[i-k]与nums[i+1]的坐标约束不满足），继续遍历。

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
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return false;
        }

        final TreeSet<Integer> values = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {

            final Integer floor = values.floor(nums[i] + t); //set中是否有满足 小于或等于 nums[i]+t 的数字
            final Integer ceil = values.ceiling(nums[i] - t); //set中是否有满足 大于或等于 nums[i]-t 的数字

            //如果有这样的数字，且TreeSet中元素坐标都与i满足约束条件，那么就有满足题意的元素

            if ((floor != null && floor >= nums[ind])
                    || (ceil != null && ceil <= nums[ind])) {
                return true;
            }

            values.add(nums[i]);
            //保证TreeSet中的坐标和i的差都小于等于k
            if (i >= k) { 
                values.remove(nums[i - k]);
            }
        }

        return false;
    }
}