博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode]Contains Duplicate II
阅读量:2236 次
发布时间:2019-05-09

本文共 684 字,大约阅读时间需要 2 分钟。

解题思路:
用 unordered_map构建逆向hash表,所以逆向,就是指把index当成value,把value当成index。这样,当value第二次出现时,可以在hash表中找到上次出现的index。比较这两个index的diff。即可得到答案。
这里有个贪心的思想,就是相邻的两个相等数的index的diff一定比不相邻的小!
前条件:unordered_map<int, int> , 
不变式:比较k与 同一个数的两个index的差值diff
结束条件:diff <= k

临界条件:nums长度大于1呗! 

class Solution {public:    bool containsNearbyDuplicate(vector
& nums, int k) { if (nums.size() <= 1) return false; unordered_map
hashTable; for (int i = 0; i < nums.size(); ++i){ if ((hashTable.find(nums[i]) != hashTable.end()) && (i - hashTable[nums[i]]) <= k) return true; hashTable[nums[i]] = i; } return false; }};

转载地址:http://yjpbb.baihongyu.com/

你可能感兴趣的文章
Java集合详解4:一文读懂HashMap和HashTable的区别以及常见面试题
查看>>
Java集合详解5:深入理解LinkedHashMap和LRU缓存
查看>>
Java集合详解6:这次,从头到尾带你解读Java中的红黑树
查看>>
Java集合详解8:Java集合类细节精讲,细节决定成败
查看>>
Java并发指南1:并发基础与Java多线程
查看>>
Java并发指南2:深入理解Java内存模型JMM
查看>>
Java并发指南5:JMM中的final关键字解析
查看>>
Java并发指南6:Java内存模型JMM总结
查看>>
Java并发指南7:JUC的核心类AQS详解
查看>>
Java并发指南8:AQS中的公平锁与非公平锁,Condtion
查看>>
Java网络编程和NIO详解6:Linux epoll实现原理详解
查看>>
Java网络编程和NIO详解7:浅谈 Linux 中NIO Selector 的实现原理
查看>>
Java网络编程与NIO详解8:浅析mmap和Direct Buffer
查看>>
Java网络编程与NIO详解10:深度解读Tomcat中的NIO模型
查看>>
Java网络编程与NIO详解11:Tomcat中的Connector源码分析(NIO)
查看>>
深入理解JVM虚拟机1:JVM内存的结构与消失的永久代
查看>>
深入理解JVM虚拟机3:垃圾回收器详解
查看>>
深入理解JVM虚拟机4:Java class介绍与解析实践
查看>>
深入理解JVM虚拟机5:虚拟机字节码执行引擎
查看>>
深入理解JVM虚拟机6:深入理解JVM类加载机制
查看>>