跳到主要内容

剑指 Offer II 057.值和下标之差都在给定的范围内

· 阅读需 3 分钟

1、题干​

给你一个整数数组 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

示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

 

提示：

  • 0 <= nums.length <= 2 * 104
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 104
  • 0 <= t <= 231 - 1

 

注意：本题与主站 220 题相同： https://leetcode-cn.com/problems/contains-duplicate-iii/

2、解法1-暴力解法​

双层遍历，外层从头到尾遍历，内层遍历外层元素之后的 k 个元素，如果找到两个元素差值的绝对值小于等于 t 则结果为 true。

注意：内层只需要遍历后 k 个元素，因为前 k 个元素在外层遍历时已经判断过

3、复杂度​

  • 时间复杂度：O(nk)O(nk)
  • 空间复杂度：O(1)O(1)

4、代码​

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= i + k && j < nums.length; j++) {
            if (Math.abs(nums[j] - nums[i]) <= t) return true;
        }
    }
    return false;
};

5、执行结果​

执行用时: 500 ms 内存消耗: 39.1 MB

6、解法2-桶排序​

遍历过程中使用桶排序维护 k 个元素的有序集合，桶的大小设置为 t + 1 以保证同一个桶内出现两个元素 n1 和 n2 时，必定有 abs(n1 - n2) <= t 即结果为true，另外如果相邻的桶内有数字且满足与当前数字的差值的绝对值小于等于 t 则结果为 true。

7、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(k)O(k)

8、代码​

var containsNearbyAlmostDuplicate = function (nums, k, t) {
    const buckets = new Map();
    const genIdx = (n) => ((n + 2147483648) / (t + 1)) >> 0;

    for (let i = 0; i < nums.length; i++) {
        if (i > k) buckets.delete(genIdx(nums[i - k - 1]));
        const idx = genIdx(nums[i]);
        if (buckets.has(idx)) return true;
        if (buckets.has(idx - 1) && nums[i] - buckets.get(idx - 1) <= t) return true;
        if (buckets.has(idx + 1) && buckets.get(idx + 1) - nums[i] <= t) return true;
        buckets.set(idx, nums[i]);
    }

    return false;
};

9、执行结果​

image.png