每天一算:Contains Duplicate II

Contains Duplicate II

leetcode上第219号问题:Contains Duplicate II

给出⼀个整形数组nums和⼀个整数k,是否存在索引i和j,使得nums[i] == nums[j] 且i和j之间的差不超过k Example 1: Input: nums = [1,2,3,1], k = 3 Output: true. Example 2: Input: nums = [1,0,1,1], k = 1 Output: true Example 3: Input: nums = [1,2,3,1,2,3], k = 2 Output: false

思路

考虑用滑动窗口与查找表来解决。

  • 设置查找表record,用来保存每次遍历时插入的元素,record的最大长度为k
  • 遍历数组nums,每次遍历的时候在record查找是否存在相同的元素,如果存在则返回true,遍历结束
  • 如果此次遍历在record未查找到,则将该元素插入到record中,而后查看record的长度是否为k + 1
  • 如果此时record的长度是否为k + 1,则删减record的元素,该元素的值为nums[i - k]
  • 如果遍历完整个数组nums未查找到则返回false

动画演示

动画演示

代码

 1// 219. Contains Duplicate II
 2// https://leetcode.com/problems/contains-duplicate-ii/description/
 3// 时间复杂度: O(n)
 4// 空间复杂度: O(k)
 5class Solution {
 6public:
 7    bool containsNearbyDuplicate(vector<int>& nums, int k) {
 8
 9        if(nums.size() <= 1)  return false;
10
11        if(k <= 0)  return false;
12
13
14        unordered_set<int> record;
15        for(int i = 0 ; i < nums.size() ; i ++){
16
17            if(record.find(nums[i]) != record.end()){
18                return true;
19            }
20
21            record.insert(nums[i]);
22
23            // 保持record中最多有k个元素
24            // 因为在下一次循环中会添加一个新元素,使得总共考虑k+1个元素
25            if(record.size() == k + 1){
26                record.erase(nums[i - k]);
27            }
28        }
29
30        return false;
31    }
32};

执行结果

执行结果

原文发布于微信公众号 - 五分钟学算法(blgczzz)

原文发表时间:2018-11-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

Go语言interface详解

interface Go语言里面设计最精妙的应该算interface,它让面向对象,内容组织实现非常的方便,当你看完这一章,你就会被interface的巧妙设计...

3697
来自专栏行者常至

003.golang 类型与变量

零值并不等于空值,而是当变量被声明为某种类型后的默认值, 通常情况下值类型的默认值为0,bool为false,string为空字符串

782
来自专栏从流域到海域

Python set(集合) 这一定是最全的介绍集合的博文

Python的set是一个无序且无重复元素的集合,概念上相当于数学上的无序集,数据结构上相当于dict的键。 既然set是集合,则必然可以实现并、交、...

2155
来自专栏学海无涯

14.闭包

951
来自专栏企鹅号快讯

bash shell 中如何区别$和${}和$和

$()和${}的用法: 在 bash shell 中,$( ) 与 ` ` (反引号) 都是用来做命令替换用(command substitution)的。而...

35016
来自专栏Java帮帮-微信公众号-技术文章全总结

04-02.总结switch,for,while,do。while跳转语句

(4)do...while循环 A:基本格式 do { 循环体语句; }while(判断条件语句); 扩展格式: 初始化语句; do { 循环体语...

3824
来自专栏轮子工厂

2. C语言 -- printf 的花式操作

(。・∀・)ノ゙嗨!大家好,我是呆博~很开心可以在这里给接着大家分享我的 C 语言学习笔记~因为微信对于代码块的支持并不是很好,所以代码部分以截图形式呈现,如果...

2817
来自专栏Script Boy (CN-SIMO)

Qt Quick编程(1)——QML的核心部分ECMAScript

说道QML,不得不先说一下ECMAScript: ECMAScript语言的标准是由Netscape、Sun、微软、Borland等公司基于JavaScript...

3920
来自专栏Golang语言社区

Go语言interface详解

interface Go语言里面设计最精妙的应该算interface,它让面向对象,内容组织实现非常的方便,当你看完这一章,你就会被interface的巧妙设计...

3679
来自专栏柠檬先生

JavaScript 基础(一)

基本语法: 区分大小写:       ECMAScript 中的一切(变量,函数名和操作符)都区分大小写。 标识符:     表示符就是指,变量,函数,属性...

20910

扫码关注云+社区