[LeetCode] 128. Longest Consecutive Sequence (java)

https://leetcode.com/problems/longest-consecutive-sequence/description/

 

 

문제 파악

정렬되지 않은 정수 배열 nums가 주어질 때, 배열의 원소들로 연속된 수열을 만들려고 한다. 만들 수 있는 가장 긴 수열의 길이를 return하라.

단, 알고리즘이 O(n) 시간 내에 수행되도록 작성해야 한다.

 

 

문제 풀이

HashSet

class Solution {
    public int longestConsecutive(int[] nums) {
        int answer = 0;
        Set<Integer> hashSet = new HashSet<>();
        
        for (int num : nums) {
            hashSet.add(num);
        }

        for (int num : hashSet) {
            int count = 1;
            if (!hashSet.contains(num - 1)) {
                int nextNum = num;
                while (true) {
                    if (hashSet.contains(++nextNum)) {
                        count++;
                    }
                    else {
                        break;
                    }   
                }
            }
            
            if (count > answer) answer = count;
        }
        
        return answer;
    }
}

 

📊 실행 결과

• Time Complexity: O(n) time