[Easy] LeetCode - no.219 Contains Duplicate II : Java

https://leetcode.com/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

int 배열 nums가 주어졌을 때, 똑같은 숫자끼리의 인덱스 차이가 k 이하인지 여부 판단

Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false

 

 

 

풀이1

    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = map.getOrDefault(nums[i], new ArrayList<>());
            list.add(i);

            map.put(nums[i], list);
        }

        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();

            for (int i = 0; i < list.size() - 1; i++) {
                min = Math.min(min, list.get(i + 1) - list.get(i));
            }
        }

        return min <= k;
    }

• HashMap 사용 : 이 때 value를 List<Integer>로 설정
• 인덱스 값의 차이의 최소값을 저장하기 위한 min 변수
• for문으로 nums 순회
  • nums[i]가 map에 존재한다면 해당 list를 찾아오고, 아니라면 새로운 ArrayList를 선언
  • list에 i 라는 인덱스 값 저장
  • map.put()
• Entry를 사용하여 list를 하나씩 가져옴
  • list를 순회하며 앞 뒤 인덱스 값의 차이의 최소값을 min에 저장
• min <= k 반환
• 시간복잡도 : O(N)

 

 

풀이2

    public boolean containsNearbyDuplicate2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && (i - map.get(nums[i])) <= k) {
                return true;
            }

            map.put(nums[i], i);
        }

        return false;
    }

• HashMap 사용
• for문으로 nums 순회
  • map이 nums[i]라는 key값을 가지고 있고, 현재 인덱스(i) - 이전 인덱스(map.get(nums[i]))의 값이 k 이하라면 true 반환
  • map.put() : key - nums[i], value - i (인덱스)
• 시간복잡도 : O(N)

💬 훨씬 깔끔한 코드, 메모리 차지도 줄어듦