首页 > 代码库 > leetcode Longest Consecutive Sequence
leetcode Longest Consecutive Sequence
给定一个数组，找出里面连续的子序列的最长长度。例如：
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
思路一：排序，然后count一下就ok了，但都懒得试了，一点技术含量都没有。
思路二：利用counting sort，但是实现的时候哈哈，果然，数太大，需要的空间太大，failed。
思路三：利用hash，c++11里用unordered_map或者set，然后想采用first和second的方法，如果hash插入后再里面自动排序了，那么用一个迭代器遍历就行了。虽然还是不行。但是起码学会了如何遍历一个hash表。就是用迭代器。
思路四：终于行的通了。还是利用hash将数组映射后，遍历一边给定的数组，对每个数在hash里面找left和right就是多1或者少1，然后记录个数cnt，返回最大的cnt即可。注意的是每次遍历需要对hash表的存在的要删除，这样的话才可能是O(n), 否则会出现n方的，例如：[1,2,3,4]的时候对每个都要找就是n方了，但是如果每次找的时候删除就可以做到O(n)了。
代码如下：
class Solution {public: int longestConsecutive(vector<int> &num) { int len = num.size(); if (len == 0 || len == 1) return len; unordered_map<int, int> umap; for (int i = 0; i < len; i++) { umap[num[i]]++; } int ans = 0; for (int i = 0; i < len; i++) { int cnt = 1; if (umap.count(num[i]) > 0) { int left = num[i] - 1, right = num[i] + 1; while(umap.count(left)) { cnt++; umap.erase(left); left--;} while(umap.count(right)) {cnt++; umap.erase(right);right++;} } if (cnt > ans) ans = cnt; } return ans; }};
leetcode Longest Consecutive Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。