LeetCode - Check If N and Its Double Exist (Searching)

algorithm

문제 : 배열이 주어졌을 때, 배열에 N과 2*N이 존재하는지 찾는 문제

LeetCode - Check If N and Its Double Exist에서 문제를 풀어볼 수 있습니다.

Example

Ex 1.

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Ex 2.

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Constraints

2 <= arr.length <= 500
-10^3 <= arr[i] <= 10^3

Soultion

  1. 1개의 for문으로 HashMap에 N의 2배수를 key로, Index를 Value로 저장
  2. 1개의 for문으로 HashMap에 N이 존재하는지 확인, Map에 N이 있다면 N의 2배수가 arr에 존재한다는 의미
  3. 0의 경우 2배수도 0이다. 이런 경우 Map에서 리턴되는 Index로 동일 객체인지 확인
  4. O(2n)으로 처리
class Solution {
	public boolean checkIfExist(int[] arr) {
        HashMap<Integer, Integer> hash = new HashMap<>();
        for (int i=0; i < arr.length; i++) {
        	hash.put(arr[i]*2, i);
        }
        for (int i=0; i < arr.length; i++) {
        	Integer index = hash.get(arr[i]);
        	if (index != null && index != i) {
        		return true;
        	}
        }
        return false;
    }
}
Loading script...
codechachaCopyright ©2019 codechacha