题目描述(中等难度)

220*. Contains Duplicate III - 图1

判断是否存在两个数,下标之间相差不超过 k,并且两数相差不超过 t

先做一下 219. Contains Duplicate II ,再做这个题可能更有感觉。

解法一 暴力

两层循环,判断当前数字和下标相距它 k 内的数是否存在数值相差不超过 t 的。

  1. public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  2. int n = nums.length;
  3. for (int i = 0; i < n; i++) {
  4. for (int j = 1; j <= k; j++) {
  5. if (i + j >= n) {
  6. break;
  7. }
  8. if (Math.abs(nums[i] - nums[i + j]) <= t) {
  9. return true;
  10. }
  11. }
  12. }
  13. return false;
  14. }

上边的看似没有什么问题,但对于一些数相减可能会产生溢出,比如 Integer.MAX_VALUE - (-2) 就会产生溢出了,一些溢出可能导致我们最终的结果出问题。关于为什么产生溢出可以参考 趣谈补码

最直接的解决方案,也是最偷懒的方案,题目中给我们的数据是 int,我们强制转为 long 进行运算,就不会出错了。

  1. public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  2. int n = nums.length;
  3. for (int i = 0; i < n; i++) {
  4. for (int j = 1; j <= k; j++) {
  5. if (i + j >= n) {
  6. break;
  7. }
  8. if (Math.abs((long) nums[i] - nums[i + j]) <= t) {
  9. return true;
  10. }
  11. }
  12. }
  13. return false;
  14. }

题目到这里已经解决了,我们再多思考一下,不借助 long 可以做吗?

两数相减然后取绝对值出现了溢出,也就意味着绝对值的结果大于了 Integer.MAX_VALUE,而 t <= Integer.MAX_VALUE,也就意味着此时两数相差不满足小于等于 t 的条件。

换句话讲,如果两数相减取绝对值产生了溢出,那么此时结果一定是大于 t 的,可以直接跳过。

因此,接下来只需要解决怎么判断是否产生溢出即可。

两数相减有四种情况。

  • 正数减正数,不会产生溢出。

  • 正数减负数,结果一定是正数,如果此时结果是负数,说明出现了溢出。

  • 负数减正数,结果一定是负数,如果此时结果是正数,说明出现了溢出。这里还有一种特殊情况需要考虑,我们知道负数比正数多一个。最小的负数是 -2147483648,最大的正数是 2147483647

    如果我们计算 -2147483647 - 1 = -2147483648,虽然结果没有溢出,但如果取绝对值,由于正数不能表示 2147483648 ,所以这种情况也需要看成溢出。

  • 负数减负数,不会产生溢出。

代码的话,考虑可能产生溢出的两种情况即可。

  1. public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  2. int n = nums.length;
  3. for (int i = 0; i < n; i++) {
  4. for (int j = 1; j <= k; j++) {
  5. if (i + j >= n) {
  6. break;
  7. }
  8. int sub = nums[i] - nums[i + j];
  9. //正数减负数, 0 算作正数,因为 0 - (-2147483648) 会出现溢出
  10. if (nums[i] >= 0 && nums[i + j] < 0) {
  11. if (sub < 0) {
  12. continue;
  13. }
  14. }
  15. //负数减正数
  16. if (nums[i] < 0 && nums[i + j] >= 0) {
  17. if (sub > 0 || sub == Integer.MIN_VALUE) {
  18. continue;
  19. }
  20. }
  21. if (Math.abs(sub) <= t) {
  22. return true;
  23. }
  24. }
  25. }
  26. return false;
  27. }

但是这个解法竟然超时了,百思不得其解,,,大家谁知道可以告诉我为什么。

解法二

考虑下算法的优化,受 219 题 的启发,利用一个滑动窗口,我们只考虑当前数前边的窗口内情况。那么问题来了,比较窗口内的什么呢?

如果我们知道窗口内的最大值和最小值,那就可以优化一下算法,举个例子。

  1. k = 3, t = 2, 窗口内 3 个数,当前考虑 x
  2. 2 6 3 x 5
  3. ^ ^
  4. 窗口内的数是 2 6 3,最大数是 max, 最小数是 min
  5. 我们把 x 和最大数和最小数比较
  6. 如果 x >= max, 那么如果 x max 的差大于了 t, 那么和窗口内的其他数的差肯定都大于 t, 也就不需要判断了
  7. 如果 x <= min, 那么如果 min x 的差大于了 t, 那么窗口内的其他数和它的差肯定都大于 t, 也就不需要判断了
  8. 如果 min < x < max, 这样的话就只能按照解法一暴力的方式,一个一个判断了
  9. 如果没有找到符合条件的解, 那么就将窗口中的第一个数删除, x 加入窗口后继续判断
  10. 2 6 3 x 5
  11. ^ ^
  12. 继续考虑 5 和窗口内最大数和最小数的情况。

上边的分析,我们需要得到最大数和最小数,以及从窗口内删除数。受 218 题 启发,我们可以用两个 TreeMap ,这样得到最大数或者最小数时间复杂度是 O(log(n)),以及删除一个数字也是 O(log(n))

  1. public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  2. //为了得到窗口内的最大数
  3. TreeMap<Integer, Integer> maxTreeMap = new TreeMap<>(new Comparator<Integer>() {
  4. @Override
  5. public int compare(Integer i1, Integer i2) {
  6. return i2 - i1;
  7. }
  8. });
  9. //为了得到窗口内的最小数
  10. TreeMap<Integer, Integer> minTreeMap = new TreeMap<>();
  11. int n = nums.length;
  12. if (n == 0) {
  13. return false;
  14. }
  15. maxTreeMap.put(nums[0], 1);
  16. minTreeMap.put(nums[0], 1);
  17. for (int i = 1; i < n; i++) {
  18. //将窗口内的第一个数删除
  19. if (i > k) {
  20. remove(maxTreeMap, nums[i - k - 1]);
  21. remove(minTreeMap, nums[i - k - 1]);
  22. }
  23. if (maxTreeMap.size() == 0) {
  24. continue;
  25. }
  26. long max = maxTreeMap.firstKey();
  27. long min = minTreeMap.firstKey();
  28. //和最大数以及最小数进行比较
  29. if (nums[i] >= max) {
  30. if (nums[i] - max <= t) {
  31. return true;
  32. }
  33. } else if (nums[i] <= min) {
  34. if (min - nums[i] <= t) {
  35. return true;
  36. }
  37. } else {
  38. for (int j = 1; j <= k; j++) {
  39. if (i - j < 0) {
  40. break;
  41. }
  42. if (Math.abs((long) nums[i] - nums[i - j]) <= t) {
  43. return true;
  44. }
  45. }
  46. }
  47. //当前数加入窗口
  48. add(maxTreeMap, nums[i]);
  49. add(minTreeMap, nums[i]);
  50. }
  51. return false;
  52. }
  53. private void add(TreeMap<Integer, Integer> treeMap, int num) {
  54. // TODO Auto-generated method stub
  55. Integer v = treeMap.get(num);
  56. if (v == null) {
  57. treeMap.put(num, 1);
  58. } else {
  59. treeMap.put(num, v + 1);
  60. }
  61. }
  62. private void remove(TreeMap<Integer, Integer> treeMap, int num) {
  63. // TODO Auto-generated method stub
  64. Integer v = treeMap.get(num);
  65. if (v == 1) {
  66. treeMap.remove(num);
  67. } else {
  68. treeMap.put(num, v - 1);
  69. }
  70. }

遗憾的是,对于 leetcode 的 test cases,这个解法并没有带来时间上的提升,时间甚至比解法一的暴力还慢。在中国站返回了超时错误,美国站可以 AC 。

解法三 set

参考 这里-with-simple-explanation.) 。

这个方法的前提是对 TreeSet 这个数据结构要了解。其中有一个方法 public E ceiling(E e) ,返回 treeSet 中大于等于 e 的元素中最小的元素,如果没有大于等于 e 的元素就返回 null

还有一个对应的方法,public E floor(E e),返回 treeSet 中小于等于 e 的元素中最大的元素,如果没有小于等于 e 的元素就返回 null

并且两个方法的时间复杂度都是 O(log(n))

知道了这个就好说了,我们依旧是解法二那样的滑动窗口,举个例子。

  1. k = 3, t = 2, 窗口内 3 个数用 TreeSet 存储, 当前考虑 x
  2. 2 6 3 x 5
  3. ^ ^

此时我们去寻找窗口中是否存在 x - t ~ x + t 的元素。

如果我们调用 ceilling(x - t) 返回了 cc 是窗口内大于等于 x - t 中最小的数。 只要 c 不大于 x + t, 那么 c 一定是我们要找的了。否则的话,窗口就继续右移。

代码的话,由于溢出的问题,运算的时候我们直接用 long 强转。

  1. public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  2. TreeSet<Long> set = new TreeSet<>();
  3. int n = nums.length;
  4. for (int i = 0; i < n; i++) {
  5. if (i > k) {
  6. set.remove((long)nums[i - k - 1]);
  7. }
  8. Long low = set.ceiling((long) nums[i] - t);
  9. //是否找到了符合条件的数
  10. if (low != null && low <= (long)nums[i] + t) {
  11. return true;
  12. }
  13. set.add((long) nums[i]);
  14. }
  15. return false;
  16. }

解法四 map

参考 这里-time-O(n)-space-using-buckets)。

运用到了桶排序的思想,在 164 题 也使用过桶排序的思想。

首先还是滑动窗口的思想,一个窗口一个窗口考虑。

不同之处在于,我们把窗口内的数字存在不同编号的桶中。每个桶内存的数字范围是 t + 1 个数,这样做的好处是,桶内任意两个数之间的差一定是小于等于 t 的。

  1. t = 2, 每个桶内的数字范围如下
  2. 编号 ... -2 -1 0 1 ...
  3. ------- ------- ------- -------
  4. 桶内数字范围 | -6 ~ -4 | | -3 ~ -1 | | 0 ~ 2 | | 3 ~ 5 |
  5. ------- ------- ------- -------

有了上边的桶,再结合滑动窗口就简单多了,同样的举个例子。

  1. k = 3, t = 2, 窗口内 3 个数用上边的桶存储, 当前考虑 x
  2. 2 6 3 x 5
  3. ^ ^
  4. 桶中的情况
  5. 0 1 2
  6. ------- ------- -------
  7. | 2 | | 3 | | 6 |
  8. ------- ------- -------

接下来我们只需要算出来 x 在哪个桶中。

如果 x 所在桶已经有数字了,那就说明存在和 x 相差小于等于 t 的数。

如果 x 所在桶没有数字,因为与 x 所在桶不相邻的桶中的数字与 x 的差一定大于 t,所以只需要考虑与 x 所在桶相邻的两个桶中的数字与 x的差是否小于等于 t

如果没有找到和 x 相差小于等于 t 的数, 那么窗口右移。从桶中将窗口中第一个数删除, 并且将 x 加入桶中

接下来需要解决怎么求出一个数所在桶的编号。

  1. //w 表示桶中的存储数字范围的个数
  2. private long getId(long num, long w) {
  3. if (num >= 0) {
  4. return num / w;
  5. } else {
  6. //num 加 1, 把负数移动到从 0 开始, 这样算出来标号最小是 0, 已经用过了, 所以要再减 1
  7. return (num + 1) / w - 1;
  8. }
  9. }

「桶」放到代码中我们要什么数据结构存储呢?我们注意到,桶中其实最多就只会有一个数字(如果有两个数字,说明我们已经找到了相差小于等于 t 的数,直接结束)。所以我们完全可以用一个 mapkey 表示桶编号,value 表示桶中当前的数字。

同样的,为了防止溢出,所有数字我们都用成了 long

  1. public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  2. if (t < 0) {
  3. return false;
  4. }
  5. HashMap<Long, Long> map = new HashMap<>();
  6. int n = nums.length;
  7. long w = t + 1; // 一个桶里边数字范围的个数是 t + 1
  8. for (int i = 0; i < n; i++) {
  9. //删除窗口中第一个数字
  10. if (i > k) {
  11. map.remove(getId(nums[i - k - 1], w));
  12. }
  13. //得到当前数的桶编号
  14. long id = getId(nums[i], w);
  15. if (map.containsKey(id)) {
  16. return true;
  17. }
  18. if (map.containsKey(id + 1) && map.get(id + 1) - nums[i] < w) {
  19. return true;
  20. }
  21. if (map.containsKey(id - 1) && nums[i] - map.get(id - 1) < w) {
  22. return true;
  23. }
  24. map.put(id, (long) nums[i]);
  25. }
  26. return false;
  27. }
  28. private long getId(long num, long w) {
  29. if (num >= 0) {
  30. return num / w;
  31. } else {
  32. return (num + 1) / w - 1;
  33. }
  34. }

解法一暴力比较常规,解法二我应该是在潜意识中受到 164 题 的启发,用到了最大值和最小值,但对当前题并没有起到决定性的优化作用。

解法三的话,知道 treeSetceiling 方法很关键。并且思想也很棒,我们并没有去判断窗口中的数是否满足和当前数相差小于等于 t。而是反过来,去寻找满足条件的数字在窗口中是否存在。这种思维的逆转,在解题中也经常用到。

解法四的话,通过对数字的映射,从而将一部分数映射到一个 id ,进而通过 map 解决问题,很厉害。

后三种方法其实都是和滑动窗口有关,通过滑动窗口,我们保证了两个数字的下标一定是小于等于 k 的。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情