---
title: " Longest Consecutive Sequence"
author: "KickCode"
date: "2016-02-11T03:44:48Z"
tags: []
categories: ["编程语言"]
slug: "longest-consecutive-sequence"
draft: false
lastmod: "2016-02-11T03:46:01Z"
id: 2276147
url: "https://kickcode.iteye.com/blog/2276147"
---

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given ,
The longest consecutive elements sequence is . Return its length: 4.

Your algorithm should run in O(n) complexity.

题目要求我们用O(n)的时间复杂度来解决，我们可以采用并查集的思想，当扫描到一个元素，我们从当前元素的两边开始处理，如果连续的都进行标记，同时维护一个最大值，再次扫描的时候如果被标记过的就可以跳过，这样我们就可以在O(n)的时间复杂度下找到最长的连续序列。代码如下：

```java

public class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null) return 0;
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        int max = 1;
        for(int i : nums) hm.put(i, 0);
        
        for(int i = 0; i < nums.length; i++) {
            int count = 1;
            int left = -1;
            int right = 1;
            if(hm.get(nums[i]) == 1) continue;
            hm.put(nums[i], 1);
            while(hm.containsKey(nums[i] + left)) {
                hm.put(nums[i] + left, 1);
                count ++;
                left --;
            }
            while(hm.containsKey(nums[i] + right)) {
                hm.put(nums[i] + right, 1);
                count ++;
                right ++;
            }
            max = Math.max(max, count);
        }
        return max;
    }
}

```