[Array & Hash] Contains Duplicate

문제

---

정수 배열이 주어지면 배열에 값이 두 번 이상nums 나타나는지 반환 하고 모든 요소가 고유한지 반환합니다.

예시 1:

입력: nums = [1,2,3,1]
출력: true

예시 2:

입력: nums = [1,2,3,4]
출력: false

---

내 제출 코드

class Solution {
    public boolean containsDuplicate(int[] nums) {
        boolean result = true;

        for (int i = 0; i < nums.length; i++) {
                for (int j = i+1; j < nums.length; j++) {
                    if (nums[i] == nums[j]) {
                        return result = true;
                    } else return result = false;
                }
            }
            return result;
    }
}

결과

입력: nums = [1,2,3,1]

Output -> flase
Expected -> true

---

오답노트

1. else return result = false; 부분에서 문제.
   첫 번째 요소가 두 번째 요소와 다를 때 바로 false 를 반환하기 때문에 배열의 모든 요소를 제대로 확인할 수 없음. 모든 비교가 끝난 뒤 실행되어야 함.

2. 바로 true 와 false 를 반환할 수 있기 때문에 result 변수를 사용하지 않아도 됨

for (int i = 0; i < nums.length; i++) {
                for (int j = i+1; j < nums.length; j++) {
                    if (nums[i] == nums[j]) {
                        return true;
                    }
                }
            }
            return false;

---

다른 풀이

• 위 풀이는 하나의 원소 선택 시 나머지 원소를 모두 방문 : O(N^2)
• HashSet을 통해 각 요소를 한 번씩만 검사하여 시간복잡도 O(N) 으로 풀이
  (* N 은 배열 nums 의 길이)

public boolean containsDuplicate2(int[] nums) {
            Set<Integer> set = new HashSet<>(); // 추가적인 공간 필요

            for (int num : nums) { // HashSet 에 요소를 추가하면서
                if (set.contains(num)) { // 이미 존재하는지 검사
                    return true; // 중복이면 true
                }
                set.add(num);
            }
            return false; // 중복이 없다면 false
        }