LeetCode OJ:Contains DuplicateII(是否包含重复II)
2024-08-27 23:00:49
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.
这题上上一篇博客的延伸,问的是k长的距离内有没有两个数是相等的,类似一个滑动窗口问题,方法比较简单,使用一个map记下上次数出现的位置就可以了,代码如下:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
map<int, int> ret;
int sz = nums.size();
for (int i = ; i < sz; ++i){
if (ret.find(nums[i]) != ret.end() && i - ret[nums[i]] <= k)
return true;
else
ret[nums[i]] = i;
}
return false;
}
};
java版本的代码如下所示,用的方法都是一样的:
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> m = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; ++i){
if(m.containsKey(nums[i]))
if(i-m.get(nums[i]) <= k)
return true;
m.put(nums[i], i);//放在这里有两个原因,如果本来存在将index更新到最近的位置,如果不存在就将它放到map中起
}
return false;
}
}
最新文章
- spring 官方下载地址(Spring Framework 3.2.x&;Spring Framework 4.0.x)
- python中raw_input() 与 input()
- List对象分组排序算法
- 【转】TCP协议中的三次握手和四次挥手(图解)
- 转:CSS布局:Float布局过程与老生常谈的三栏布局
- [转载]Linux LVM硬盘管理及LVM扩容
- centos5.5用phpstudy一键安装配置虚拟主机后,yum配置代理服务器squid
- Week11(11月18日)
- android 去除标题
- 探索Android该Parcel机制(上)
- struts.xml在Action配置具体解释
- 自己动手用maven构建基于SSI的java EE应用
- Redis【第一篇】安装
- 让 IE支持圆角的方法
- Cs231n课堂内容记录-Lecture 5 卷积神经网络介绍
- infinite-loading 插件
- ASP.NET MVC HtmlHelper 类的扩展方法
- .NET Core2.0 使用EF做数据操作
- HDU 2521 反素数 模拟题
- Spring源码解析(三)BeanDefinition的载入、解析和注册