掘金团队号上线，助你 Offer 临门！点击查看详情

题目描述

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在两个不同下标 i 和 j，使得 abs(nums[i] – nums[j]) <= t ，同时又满足 abs(i – j) <= k 。

如果存在则返回 true，不存在返回 false。

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
复制代码

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/co…

思路

理解题目，这是一个跟排序有关的题目，在 Java 实现数据结构中, TreeMap 可以帮助我们实现排序的功能。

代码

public class DayCode {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 1};
        int k = 3, t = 0;

        boolean ans = new DayCode().containsNearbyAlmostDuplicate(nums, k, t);
        System.out.println("ans is " + ans);
    }

    /**
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;
        TreeSet<Long> treeSet = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Long u = nums[i] * 1L;
            Long l = treeSet.floor(u);
            Long r = treeSet.ceiling(u);
            if (l != null && u - l <= t) {
                return true;
            }
            if (r != null && r - u <= t) {
                return true;
            }
            treeSet.add(u);
            if (i >= k) {
                treeSet.remove(nums[i - k] * 1L);
            }
        }

        return false;
    }
}
复制代码

总结

我们使用了 TreeSet 这种结构实现代码。TreeSet 的官方介绍如下：

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
复制代码