面试算法57：值和下标之差都在给定的范围内

题目

给定一个整数数组nums和两个正数k、t，请判断是否存在两个不同的下标i和j满足i和j之差的绝对值不大于给定的k，并且两个数值nums[i]和nums[j]的差的绝对值不大于给定的t。
例如，如果输入数组{1，2，3，1}，k为3，t为0，由于下标0和下标3对应的数字之差的绝对值为0，因此返回true。如果输入数组{1，5，9，1，5，9}，k为2，t为3，由于不存在两个下标之差小于或等于2且它们差的绝对值小于或等于3的数字，因此此时应该返回false。

分析1

首先考虑最直观的解法。可以逐一扫描数组中的每个数字。对于每个数字nums[i]，需要逐一检查在它前面的k个数字是否存在从nums[i]-t到nums[i]+t的范围内的数字。如果存在，则返回true。这种思路很容易用两个嵌套的循环实现。由于数组中的每个数字都要和k个数字进行比较，如果数组的长度为n，那么这种解法的时间复杂度是O（nk）。
接下来尝试优化时间复杂度。逐一扫描数组中的每个数字。对于每个数字nums[i]，应该先从它前面的k个数字中找出小于或等于nums[i]的最大的数字，如果这个数字与nums[i]的差的绝对值不大于t，那么就找到了一组符合条件的两个数字。否则，再从它前面的k个数字中找出大于或等于nums[i]的最小的数字，如果这个数字与nums[i]的差的绝对值不大于t，就找到了一组符合条件的两个数字。
需要从一个大小为k的数据容器中找出小于或等于某个数字的最大值及大于或等于某个数字的最小值，这正是TreeSet或TreeMap适用的场景。因为这个容器只需要保存数字，所以可以用TreeSet来保存每个数字nums[i]前面的k个数字。

解1

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        boolean result = containsNearbyAlmostDuplicate(nums, 3, 0);
        System.out.println(result);
    }

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            // 地板：返回键小于或等于给定值的最大值，如果没有则返回null
            Long lower = set.floor((long)nums[i]);
            if (lower != null && lower >= (long)nums[i] - t) {
                return true;
            }

            // 天花板：返回大于或等于给定值的最小值，如果没有则返回null
            Long upper = set.ceiling((long)nums[i]);
            if (upper != null && upper <= (long)nums[i] + t) {
                return true;
            }

            set.add((long)nums[i]);
            if (i >= k) {
                set.remove((long)nums[i - k]);
            }
        }

        return false;
    }
}

分析2

下面换一种思路来解决这个问题。由于这个题目关心的是差的绝对值小于或等于t的数字，因此可以将数字放入若干大小为t+1的桶中。例如，将从0到t的数字放入编号为0的桶中，从t+1到2t+1的数字放入编号为1的桶中。其他数字以此类推。这样做的好处是如果两个数字被放入同一个桶中，那么它们的差的绝对值一定小于或等于t。
还是逐一扫描数组中的数字。如果当前扫描到数字num，那么它将放入编号为id的桶中。如果这个桶中之前已经有数字，那么就找到两个差的绝对值小于或等于t的数字。如果桶中之前没有数字，则再判断编号为id-1和id-2的这两个相邻的桶中是否存在与num的差的绝对值小于或等于t的数字。因为其他桶中的数字与num的差的绝对值一定大于t，所以不需要判断其他的桶中是否有符合条件的数字。

解2

public class Test {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 1};
        boolean result = containsNearbyAlmostDuplicate(nums, 3, 0);
        System.out.println(result);
    }

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        Map<Integer, Integer> buckets = new HashMap<>();
        int bucketSize = t + 1;
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int id = getBucketID(num, bucketSize);

            if (buckets.containsKey(id)
                || (buckets.containsKey(id - 1) && buckets.get(id - 1) + t >= num)
                || (buckets.containsKey(id + 1) && buckets.get(id + 1) - t <= num)) {
                return true;
            }

            buckets.put(id, num);
            if (i >= k) {
                buckets.remove(getBucketID(nums[i - k], bucketSize));
            }
        }

        return false;
    }

    private static int getBucketID(int num, int bucketSize) {
        return num >= 0 ? num / bucketSize : (num + 1) / bucketSize - 1;
    }
}