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.

Solution: 用hashset。up, down记录可达到的上/下限,同时把数从hashset remove

    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Set<Integer> hashset = new HashSet<>();
        int ans = 1;
        for (int num : nums) {
            hashset.add(num);
        }
        for (int num : nums) {
            int down = num - 1;
            while (hashset.contains(down)) {
                hashset.remove(down);
                down--;
            }
            int up = num + 1;
            while (hashset.contains(up)) {
                hashset.remove(up);
                up++;
            }
            ans = Math.max(ans, up - down - 1);
        }
        return ans;
    }

results matching ""

    No results matching ""