【滑动窗口】 LCR 057. 存在重复元素 III

本文主要是介绍【滑动窗口】 LCR 057. 存在重复元素 III，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

LCR 057. 存在重复元素 III

解题思路

• 使用一个 HashMap（map）来存储元素的 ID 和元素值
• 将元素的 ID 计算为元素值除以窗口大小 w，w 的计算为 t + 1
• 遍历数组，对于每个元素：
• 检查是否存在相同 ID 的元素，如果存在，说明找到了索引差值不超过 k 的两个元素，直接返回 true
• 检查相邻的两个 ID，如果它们的差值为 1，再检查对应的元素值是否差值不超过 t，如果是，则返回 true
• 将当前元素的 ID 和值存入 map 中
• 如果当前索引大于等于 k，移除最早加入窗口的元素，即索引为 i - k 的元素
• 如果遍历完成都没有找到符合条件的元素对，则返回 false。

class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {int n = nums.length;Map<Long,Long> map = new HashMap<Long,Long>();// 存储元素ID和元素值long w = (long)t + 1;for(int i = 0; i < n; i++){long id = getId(nums[i],w);if(map.containsKey(id)){return true;}if(map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w){return true;}if(map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w){return true;}map.put(id,(long)nums[i]);if(i >= k){map.remove(getId(nums[i - k],w));}}return false;}public long getId(long x,long w){if(x >= 0){return x / w;}return (x + 1) / w - 1;}
}

这篇关于【滑动窗口】 LCR 057. 存在重复元素 III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---