leetcode 220题 存在重复元素 III
给你一个整数数组 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
思路
方法一： 暴力破解，遍历每个数，直到满足条件为止
方法二： 桶排序
代码
// 暴力破解
/**
* @param {number[]} nums
* @param {number} k
* @param {number} t
* @return {boolean}
*/
function containsNearbyAlmostDuplicate(nums, k, t) {
if (nums.length < 2) {
return false;
}
for (let i = 0; i<nums.length; i++) {
for (let j = i+1; j<nums.length; j++) {
const diff = Math.abs(nums[i] - nums[j]);
if (diff <= t && (j - i) <= k) {
return true;
}
}
}
return false;
}
// 桶排序
var containsNearbyAlmostDuplicate = function(nums, k, t) {
const n = nums.length;
const mp = new Map();
for (let i = 0; i < n; ++i) {
const x = nums[i];
const id = getID(x, t + 1);
if (mp.has(id)) {
return true;
}
if (mp.has(id - 1) && Math.abs(x - mp.get(id - 1)) <= t) {
return true;
}
if (mp.has(id + 1) && Math.abs(x - mp.get(id + 1)) <= t) {
return true;
}
mp.set(id, x);
if (i >= k) {
mp.delete(getID(nums[i - k], t + 1));
}
}
return false;
};
const getID = (x, w) => {
return x < 0 ? Math.floor((x + 1) / w) - 1 : Math.floor(x / w);
}
复杂度分析
方法一：
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
方法二：
- 时间复杂度：O(N)
- 空间复杂度：O(N)