LeetCode 220 辛苦老师了

Question

 public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        if (nums.length == 0)
            return false;

        TreeSet<Long> set = new TreeSet<>();

        for (int i = 0; i < nums.length; i++) {
            long num = nums[i];

            //num-t<= x <=num+t 查看是否存在这个x   找到大于 num-t的最小值 同时 这个值在[num-t,num+t]这个范围内就是成功的
            Long ceiling = set.ceiling((long)num - t);

            if (ceiling != null && ceiling <=(long) num + t)
                return true;

            set.add(num);
            if (set.size() == k + 1) {
                set.remove((long)nums[i - k]);
            }
        }
        return false;
    }

这里有2个问题：

1. 对于k 我们用Set存 如果遇到重复元素 那么Set.size()>=k ，按照思想这个是一定的。但是看leetcode说根据我们的判断遇到重复元素会直接true，这是为什么，我们找到合适的例子，辛苦老师帮我解释下，最好能有个例子，我动笔试试
2. 这个例子中是不可能出现负数的，但是老师在别的问答区说t可以为负数，那么对于这个例子[1,0,1,-1]
   k=1
   t=-2

-t=<|i-j|=<t [-2,2]

1-(-1)=2 其实是满足 但是会返回false 为什么?

辛苦老师！本身小白，感觉我太能问问题了，不过其实我已经看了很多解法的解释，和文章，感觉总是顺着正确的思路去走，反而会出现新的问题 辛苦老师了 ，最好能举个例子

Answer 1

liuyubobobo 2020-04-15 15:05:45

1

其实我没有特别理解的你的问题。

我们在每轮循环中，其实是在看连续的 k 个元素中，是否有一个元素，和 num 的距离在 t 以内。如果存在一个元素，和 num 相同的话，那么 set.ceiling((long)num - t) 的结果，至少为 num 本身。那么下面的判断中，ceiling <=(long) num + t 一定是真的，就返回 true 了。

找一组存在相同元素的数据试试看？

2

“这个例子中是不可能出现负数的，但是老师在别的问答区说t可以为负数。"

具体你说的是哪个值不能出现负数？这个问题中，t 不可能是负数，否则没意义。但是 num - t 可能为负数。

更正：我测了一下，问题的测试用例中，t 可能是负数。此时直接返回 false 就好了。因为 nums [i] 和 nums [j] 的差的绝对值最大为 t。而 nums [i] 和 nums [j] 的差的绝对值肯定 >= 0。所以如果 t 是负数，肯定不存在，直接返回 false 就好。

继续加油！：）

• 提问者 慕妹2978617 #1

  明白了 我说的就是t ，之前您回答了另一个提问者的问题其实应该是num-t可能为负数，我理解成了t可以为负数，所以我一直在当t=负数的问题上一直纠结，如果t可以为负数那么ceiling<=num+t 也就不成立了，不过t不能为负数一下子都通了

• liuyubobobo 回复 提问者 慕妹2978617 #2

  嗯。我刚才加了一段更正。可以看一下，t 为负数，直接返回 false 就好。

• 提问者 慕妹2978617 回复 liuyubobobo #3

  哈哈 谢谢老师 辛苦啦