220. 存在重复元素 III（JS实现）

220. 存在重复元素 III（JS实现）

1 题目

在整数数组 nums 中，是否存在两个下标 i 和 j，使得 nums [i] 和 nums [j] 的差的*对值小于等于 t ，且满足 i 和 j 的差的*对值也小于等于 ķ 。

如果存在则返回 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

链接：https://leetcode-cn.com/problems/contains-duplicate-iii

2 思路

这道题我是用土办法，用滑动窗口来做的，时间复杂度有点高，题解中有用平衡二叉树和桶排序的方法，比较巧妙，在此记录下桶排序的方法 https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iii-by-leetcode/

3代码

/**

 * @param {number[]} nums

 * @param {number} k

 * @param {number} t

 * @return {boolean}

 */

var containsNearbyAlmostDuplicate = function(nums, k, t) {

    if (nums.length === 0 || t < 0 || k < 0) return false;

    let arr = [0];

    for (let i = 1; i<nums.length; i++) {

        let index = 0;

        for (let j of arr) {

            if (i – j > k) {

                index++;

                continue;

            }

            if (Math.abs(nums[i] – nums[j]) > t) continue;

            return true;

        }

        arr = arr.slice(index);

        arr.push(i);

    }

    return false;

};