每天一算: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 条评论
登录 后参与评论

相关文章

来自专栏Python研发

JavaScript

JavaScript是一门编程语言,浏览器内置了JavaScript语言的解释器,所以在浏览器上按照JavaScript语言的规则编写相应的代码,浏览器可以解释...

16420
来自专栏HTML5学堂

获取对象具体类型的功能函数

HTML5学堂:JavaScript当中,时常会使用到typeof来进行数据类型的检测,但是我们觉得typeof不能够满足我们的需求,对于数组、函数、时间对象等...

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

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

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

51600
来自专栏雪胖纸的玩蛇日常

老男孩Python全栈开发(92天全)视频教程 自学笔记06

21360
来自专栏企鹅号快讯

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

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

362160
来自专栏Golang语言社区

Go语言interface详解

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

37570
来自专栏学海无涯

14.闭包

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

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

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

39840
来自专栏柠檬先生

JavaScript 基础(一)

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

220100
来自专栏恰童鞋骚年

剑指Offer面试题:3.替换空格

  在网络编程中,如果URL参数中含有特殊字符,如空格、'#'等,可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的...

8820

扫码关注云+社区

领取腾讯云代金券