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

2024-01-27 16:04

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



http://www.chinasem.cn/article/650768

相关文章

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

SpringBoot+Redis防止接口重复提交问题

《SpringBoot+Redis防止接口重复提交问题》:本文主要介绍SpringBoot+Redis防止接口重复提交问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录前言实现思路代码示例测试总结前言在项目的使用使用过程中,经常会出现某些操作在短时间内频繁提交。例

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中,我们经常需要让某个元素占据容器的剩余空间,本文将介绍5种不同的方法来实现这个需求,并分析各种方法的优缺点,感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中,我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Windows的CMD窗口如何查看并杀死nginx进程

《Windows的CMD窗口如何查看并杀死nginx进程》:本文主要介绍Windows的CMD窗口如何查看并杀死nginx进程问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录Windows的CMD窗口查看并杀死nginx进程开启nginx查看nginx进程停止nginx服务

C#之List集合去重复对象的实现方法

《C#之List集合去重复对象的实现方法》:本文主要介绍C#之List集合去重复对象的实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C# List集合去重复对象方法1、测试数据2、测试数据3、知识点补充总结C# List集合去重复对象方法1、测试数据

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元