[LeetCode] 128. Longest Consecutive Sequence

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

---

Solution

class Solution {
    public int longestConsecutive(int[] nums) {
        int longest = 0;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int n : nums)
            if (!map.containsKey(n)) {
                int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
                int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
                int sum = left + right + 1;
                map.put(n, sum);
                longest = Math.max(longest, sum);
                map.put(n - left, sum);
                map.put(n + right, sum);
            }
        return longest;
    }
}

Explanation

• 정렬이 되지 않은 배열 속에서 O(n) 안에 연속되는 요소를 찾으려면 반복문을 통해 배열 속 요소에 하나씩 접근하면서 배열이 정렬되도록 만들고, 그와 동시에 연속되는 요소의 개수를 찾아야 한다.
• 배열의 요소를 자료구조 Map의 Key로, 연속되는 요소의 길이를 Value로 사용하면 배열을 정렬한 것처럼 만듦과 동시에 연속되는 요소의 길이를 구할 수 있다.

• map을 선언하고 for반복문을 통해 배열 nums의 요소들을 map에 집어넣는다. 중복된 요소는 연속 길이 계산에 포함하지 않기 때문에 if조건문을 통해 중복요소를 무시하도록 해준다.

  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  for (int n : nums)
    if (!map.containsKey(n))
        map.put(n, 1);
  

• map에 요소가 추가될 때 연속된 요소가 생기면 Value값을 갱신해 주어야 하므로 map에 요소를 추가할 위치 좌우의 인접한 요소가 있는지를 확인하고 알맞은 값을 Value에 할당해주도록 한다.

  for (int n : nums)
    if (!map.containsKey(n)) {
        int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
        int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
        int sum = left + right + 1;
        map.put(n, sum);
    }
  

• 인접한 요소들에 인접하는 요소가 한 쪽에 하나 더 추가되어 Value가 갱신될 때 반대쪽 가장 멀리 위차한 요소의 Value값도 추가되는 요소의 Value값과 동일하게 갱신되어야 한다. 이를 반영하기 위하여 for반복문이 진행될 때 Value값이 갱신되도록 한다.
• 가장 긴 요소들의 길이를 나타내기 위한 변수 longest를 선언하고 for반복문이 진행되는 동안 갱신되도록 한다.

  int longest = 0;
  for (int n : nums)
    if (!map.containsKey(n)) {
        int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0;
        int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0;
        int sum = left + right + 1;
        map.put(n, sum);
        longest = Math.max(longest, sum);
        map.put(n - left, sum);
        map.put(n + right, sum);
    }
  

• 가장 긴 요소들의 길이를 나타내는 변수 longest를 반환한다.

  return longest;