Leetcode 题目解析之 Contains Duplicate III

原创

ruochen

发布于 2022-01-08 14:52:58

1.2K0

发布于 2022-01-08 14:52:58

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

对于加入的元素，要能够在O(1)时间内查找，同时还要自动排序，维持一个k个元素的TreeSet。

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0 || nums == null || nums.length < 2) {
            return false;
        }
        SortedSet<Long> set = new TreeSet<Long>();
        for (int j = 0; j < nums.length; j++) {
            SortedSet<Long> subSet = set.subSet((long) nums[j] - t,
                    (long) nums[j] + t + 1);
            // 集合不为空，则表示找到解
            if (!subSet.isEmpty()) {
                return true;
            }
            if (j >= k) {
                set.remove((long) nums[j - k]);
            }
            set.add((long) nums[j]);
        }
        return false;
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

difference