[LeetCode] 217. Contains Duplicate - Java

 

https://leetcode.com/problems/contains-duplicate/

---

문제

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

---

풀이

풀이 과정

정수 배열이 인자값으로 들어오고 그 배열 안에 중복된 수가 있는지 판단하는 문제이다
중복된 수가 존재한다면 true를 반환하고, 중복된 수가 없다면 false를 반환한다

한 번 탐색한 데이터를 저장해 놓을 Map을 선언한다

Map<Integer, Boolean> dataMap = new HashMap<>(); // 탐색한 데이터를 저장할 Map

 

입력받은 배열을 탐색하며 탐색 중인 값이 Map에 저장 되어있는 값이라면 중복이 존재하므로 바로 true를 반환하고 Map에 저장되어 있지 않은 값이라면 Map에 현재 탐색 값을 추가한 후 탐색을 계속한다

배열을 모두 탐색할 때 까지 중복값이 존재 하지 않는다면 false를 반환한다

for(int i : nums) {
    if(dataMap.containsKey(i)) { // 이미 탐색한 값인 경우 (중복이 존재)
        return true;
    } else { // 처음 탐색한 값인 경우
        dataMap.put(i, true); // 현재 값을 탐색한 데이터 Map에 저장				
    }
}

return false; // 배열을 모두 탐색 후 중복 값이 없으면 false를 return

 

현재 탐색중인 값과 그 이전 값들을 모두 비교해보아야하는 Brute force와 달리
한번 탐색한 값을 Map에 저장해 두고 탐색중인 값과 비교 하게 되면
배열에 중복된 값이 없어 모든 배열 값을 탐색하는 경우에도 배열의 길이만큼만 탐색을 하면 되기 때문에 O(n)의 시간 복잡도로 문제 해결이 가능하다

최종 코드

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Boolean> dataMap = new HashMap<>(); // 탐색한 데이터를 저장할 Map
	for(int i : nums) {
	    if(dataMap.containsKey(i)) { // 이미 탐색한 값인 경우 (중복이 존재)
	        return true;
	    } else { // 처음 탐색한 값인 경우
	        dataMap.put(i, true); // 현재 값을 탐색한 데이터 Map에 저장
	    }
        }
        return false; // 배열을 모두 탐색 후 중복 값이 없으면 false를 return
    }
}

---