import java.util.HashSet;

import java.util.Set;

/**

 * Source : https://oj.leetcode.com/problems/longest-consecutive-sequence/

 *

 *

 * Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

 *

 * For example,

 * Given [100, 4, 200, 1, 3, 2],

 * The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

 *

 * Your algorithm should run in O(n) complexity.

 */

public class LongestConsecutiveSequence {

    /**

     * 求出数组中元素能构成连续序列的最大长度

     *

     * 题目中要求是O(n)，所以不能使用排序的办法

     * 针对每个元素arr[i]寻找数组中向前、向后有没有能构成连续序列的元素，查找的时候利用hash表

     * 每次记录最大长度，如果找到了就把该元素从hash表中删除，因为该元素不会被再次查找到，所以从hash表中移除

     * 如果hash表为空了，说明所有元素都被查找过，退出循环

     *

     * @param arr

     * @return

     */

    public int findLongestSequence (int[] arr) {

        int max = 0;

        Set<Integer> set = new HashSet<Integer>(arr.length);

        for (int i = 0; i < arr.length; i++) {

            set.add(arr[i]);

        }

        for (int i = 0; i < arr.length; i++) {

            int curnum = arr[i] - 1;

            int len = 1;

            // 查找curnum左边的数字

            while (set.contains(curnum)) {

                set.remove(curnum);

                curnum -= 1;

                len++;

            }

            curnum = arr[i] + 1;

            while (set.contains(curnum)) {

                set.remove(curnum);

                curnum += 1;

                len++;

            }

            max = Math.max(max, len);

            if (set.size() <= 0) {

                return max;

            }

        }

        return max;

    }

    public static void main(String[] args) {

        LongestConsecutiveSequence longestConsecutiveSequence = new LongestConsecutiveSequence();

        System.out.println(longestConsecutiveSequence.findLongestSequence(new int[]{100, 4, 200, 1, 3, 2}) + "----4");

    }

}