[LeetCode] 128. Longest Consecutive Sequence - 해시셋(HashSet) JAVA

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

코드설명

해시셋(HashSet) 을 활용합니다.

 

처음에는 배열을 활용했지만, HashSet을 활용할경우 훨씬 간단하게 처리가 가능합니다.

HashSet을 활용할경우 메모리제한과 중복제거의 장점을 모두 가질 수 있지만, 여전히 시간초과라는 함정이 존재합니다.

어떻게 해야할까요? 만약 [100, 4, 200, 1, 3, 2] 가 존재한다고 합시다.

이떄, 1 2 3 4, 혹은 2 3 4, 혹은 3 4 혹은 4 이렇게 총 4번이 불필요하게 처리됩니다.

이때 1 2 3 4 가 가장 깁니다. 이떄 특징은, 1보다 작은 0 이 HashSet이 존재하지 않는다는점이 이 Longest answer의 특징인것을 확인할 수 있습니다. 해당값의 조건에서만 값을 반환처리합니다.

코드

정답코드1입니다.

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

        for(int i=0; i<nums.length; i++){
            int target = nums[i] - 1;
            int length = 1;
            if(hashset.contains(target) == false){
                while(hashset.contains(nums[i] + length) == true){
                    length += 1;
                }
            }
            answer = Math.max(answer, length);
        }

        return answer;
    }
}

처음에 작성한 오답 코드. 10^9 의 값을 메모리로 나타내려했길래 주소값을 나타내지 못하고 숫자가 범위값을 넘어갑니다.

class Solution {
    public int longestConsecutive(int[] nums) {
        int[] cache = new int[2*10^9 + 1];
        for(int i=0; i<nums.length; i++){ 
            cache[nums[i] + 10^9] += 1;
        }
        int idx = 0;
        int answer = 0;
        int ret = 0;
        while(idx < cache.length){
            if(cache[idx] > 0){
                ret++;
                answer = Math.max(answer, ret);
            }else if( cache[idx] == 0){
                ret = 0;
            }
            idx += 1;
        }
        return answer;
    }
}