当前位置:网站首页>Leetcode topic analysis contains duplicate III

Leetcode topic analysis contains duplicate III

2022-06-23 09:08:00 ruochen

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.

For added elements , To be able to O(1) Find... In time , At the same time, it also has to sort automatically , Maintain one k An element of 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);
            //  Set is not empty , Then the solution is found 
            if (!subSet.isEmpty()) {
                return true;
            }
            if (j >= k) {
                set.remove((long) nums[j - k]);
            }
            set.add((long) nums[j]);
        }
        return false;
    }
原网站

版权声明
本文为[ruochen]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/01/202201081604220962.html