题目

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

Example 1:

  1. Input: nums = [1,2,3,1], k = 3, t = 0
  2. Output: true

Example 2:

  1. Input: nums = [1,0,1,1], k = 1, t = 2
  2. Output: true

Example 3:

  1. Input: nums = [1,5,9,1,5,9], k = 2, t = 3
  2. Output: false

题意

判断数组中是否存在这样一组数，它们的值之差的绝对值不大于t，且下标之差的绝对值不大于k。

思路

最简单的方法是直接遍历，再判断当前数与它之后的k个数的差值是否符合条件。

优化的方法是借助红黑树实现滑动窗口思想：在红黑树中只保存k+1个连续的数(这样就控制了树中所有数的下标差不大于k)，每次加入新数时，先去除一个数(容量已到达k+1的情况下)，在树中找到小于新数的最大数和大于新数的最小数，判断它们与新数的差是否满足条件，最后将新数加入红黑树中。

代码实现

Java

暴力法

  1. class Solution {
  2.     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  3.         if (t < 0) {
  4.             return false;
  5.         }
  7.         for (int i = 0; i < nums.length; i++) {
  8.             for (int j = i + 1; j <= Math.min(i + k, nums.length - 1); j++) {
  9.                   // 不转化为long可能会有溢出
  10.                 if (Math.abs((long) nums[i] - (long) nums[j]) <= (long) t) {
  11.                     return true;
  12.                 }
  13.             }
  14.         }
  16.         return false;
  17.     }
  18. }

红黑树

  1. class Solution {
  2.     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  3.         if (t < 0) {
  4.             return false;
  5.         }
  7.         TreeSet<Integer> set = new TreeSet<>();
  8.         for (int i = 0; i < nums.length; i++) {
  9.               // 保证树的容量始终不超过k+1
  10.             if (i > k) {
  11.                 set.remove(nums[i - k - 1]);
  12.             }
  13.             if (set.contains(nums[i])) {
  14.                 return true;
  15.             }
  16.               // 因为可能为null，所以必须用包装类接收
  17.             Integer lower = set.lower(nums[i]);
  18.             Integer higher = set.higher(nums[i]);
  19.               // 转换成long计算防止溢出
  20.             if (lower != null && (long) nums[i] - lower <= t
  21.                     || higher != null && (long) higher - nums[i] <= t) {
  22.                 return true;
  23.             }
  24.             set.add(nums[i]);
  25.         }
  27.         return false;
  28.     }
  29. }

JavaScript

暴力法

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @param {number} t
  5.  * @return {boolean}
  6.  */
  7. var containsNearbyAlmostDuplicate = function (nums, k, t) {
  8.   for (let i = 0; i < nums.length; i++) {
  9.     for (let j = i + 1; j <= i + k && j < nums.length; j++) {
  10.       if (Math.abs(nums[j] - nums[i]) <= t) {
  11.         return true
  12.       }
  13.     }
  14.   }
  15.   return false
  16. }

参考
very simple and clean solution on Java (72.47%))