# Longest Consecutive Sequence ### Source - leetcode: [Longest Consecutive Sequence | LeetCode OJ](https://leetcode.com/problems/longest-consecutive-sequence/) - lintcode: [(124) Longest Consecutive Sequence](http://www.lintcode.com/en/problem/longest-consecutive-sequence/) ### Problem Given an unsorted array of integers, find the length of the longestconsecutive elements sequence. #### Example Given `[100, 4, 200, 1, 3, 2]`,The longest consecutive elements sequence is `[1, 2, 3, 4]`. Return itslength: `4`. #### Clarification Your algorithm should run in O(*n*) complexity. ### 題解 首先看題要求，時間復雜度為 O(n)O(n)O(n), 如果排序，基于比較的實現為 nlognn \log nnlogn, 基數排序需要數據有特征。故排序無法達到復雜度要求。接下來可以聯想空間換時間的做法，其中以哈希表為代表。這個題要求返回最長連續序列，不要求有序，非常符合哈希表的用法。**由于給定一個數其連續的數要么比它小1，要么大1，那么我們只需往左往右搜索知道在數組中找不到數為止。**結合哈希表查找為 O(1)O(1)O(1) 的特性即可滿足要求。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return an integer */ public int longestConsecutive(int[] num) { if (num == null || num.length == 0) return 0; // add number to hashset Set<Integer> hashset = new HashSet<Integer>(); for (int n : num) { hashset.add(n); } int lcs = 0; for (int n : num) { int i = n, count = 1; hashset.remove(n); // i-- while (hashset.contains(--i)) { count++; hashset.remove(i); } // i++ i = n; while (hashset.contains(++i)) { count++; hashset.remove(i); } // update lcs lcs = Math.max(lcs, count); } return lcs; } } ~~~ ### 源碼分析 首先使用 HashSet 建哈希表，然后遍歷數組，依次往左往右搜相鄰數，搜到了就從 Set 中刪除。末尾更新最大值。 ### 復雜度分析 時間復雜度和空間復雜度均為 O(n)O(n)O(n).