本文主要是介绍【滑动窗口】 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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!