LeetCode OJ 219.Contains Duplicate 2
2024-10-02 17:54:53
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and jis at most k.
这个题目在前一个题的基础上有部分改动,对nums[i] = nums[j]出现的范围作出了规定,不是全局的,而是要求|i-j|<=k;
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>(0); for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
if(i-map.get(nums[i])<=k) return true;
}
if(map.size()>k) map.remove(nums[i-k]);
map.put(nums[i],i);
}
return false;
}
}
【二刷】二刷和一刷的变动不是很大,但是对HashMap的了解更深了。
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums.length <= 1 || k == 0) return false; Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i]) && i-map.get(nums[i]) <= k)
return true;
else map.put(nums[i], i);
}
return false;
}
}
【三刷】三刷的直接使用HashSet。遍历数组,如果当前下标已经大于k,则把set中不可能成立的数据删除掉,然后在把当前数字添加进去。如果set中已经包含该数,则会添加失败。
HashSet的add函数在添加成功返回true,在添加失败时返回false。
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}
}
最新文章
- [.net 面向对象程序设计进阶] (26) 团队开发利器(五)分布式版本控制系统Git——图形化Git客户端工具TortoiseGit
- LayaAir引擎——(八)
- python语言的优点和缺点
- ECharts中文显示为Unicode码
- 解读Hashtable
- SQL SERVER中XML查询:FOR XML指定PATH
- mongo - 升级步骤
- EF操作数据库的步骤和一些简单操作语句
- 使用GeoServer导出地图数据GeoJSON并应用
- java可供判断某字符串是什么编码的一行代码
- Java中五种遍历HashMap的方式
- ADO.NET 【实体类】【数据访问类】
- javascript的冒泡排序, 快速排序, 选择排序, 插入排序
- spring学习之三 数据库操作jdbcTemplate
- 牛气冲天的Iframe应用笔记
- POJ 2239
- Android6.0.1 移植:显示系统(一)--测试framebuffer
- CMDB后台管理(AutoServer)
- 使用struct与使用class初始化对象效率对比
- 搭建一个最简单的node服务器