[Leetcode Top Interview 150] 1. Two Sum

난이도 : easy

문제링크

• 정수형 배열이 주어짐
• 두개의 수를 조합하여 더한 값이 target이 되는 두 수를 리턴하라
• 오직 한번씩만 사용해야 함 (중복 불가)
• 출력 순서는 상관없음

 

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

 

1. 접근법

• 이중반복문을 돌면서 조합을 만듬
• 조합들중 합이 target인 인덱스들을 리턴

 

2. 의사코드

for (i .. nums.length 까지)
 for (j = i .. nums.length 까지)
 	nums[i] + nums[j] == target 이면
    i, j 리턴

 

3. 구현 코드

    public int[] myTwoSum(int[] nums, int target) {
         for (int i = 0; i < nums.length; i++) {
             for (int j = i+1; j < nums.length; j++) {
                 if (nums[i] + nums[j] == target) {
                     return new int[]{i, j};
                 }
             }
         }

         return null;
    }

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n^2) - n개의 원소를 이중 반복하므로
• 공간복잡도 : O(1) - 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘

 

5. 개선점

어떻게 시간복잡도를 줄일수 있을까..

배열로 경우를 0보다 큰 수와 0보다 작은수로 해보았지만 크기 범위가 40000000 이므로 Memory Limit Exceeded 되었다

        boolean[] positiveVisit = new boolean[1000000000];
        boolean[] negativeVisit = new boolean[1000000000];        

        int[] positiveIdx = new int[1000000000];
        int[] negativeIdx = new int[1000000000];
        
        for (int i = 0; i < nums.length; i++) {            
            int val = nums[i];

            if (target == 0) {
                if (val >= 0 && positiveVisit[val]) {
                    return new int[]{positiveIdx[val], i};
                }

                if (val < 0 && negativeVisit[nums[val*-1]]) {
                    return new int[]{negativeIdx[val], i};
                }
            }

            if (val >= 0) {
                positiveVisit[val] = true;
                positiveIdx[val] = i;
            } else {
                negativeVisit[val*-1] = true;
                negativeIdx[val*-1] = i;
            }
        }

        for (int i = 0; i < nums.length; i++) { 
            int val = nums[i];
            int complement = target-val;

            if (complement >= 0 && positiveVisit[complement] && positiveIdx[complement] != i) {
                return new int[]{positiveIdx[complement], i};
            }

            if (complement < 0 && negativeVisit[complement*-1] && negativeIdx[complement*-1] != i) {
                return new int[]{negativeIdx[complement*-1], i};
            }            
        }

 

6. 회고

도저히 생각이 안나서 강의를 들었다

Map<Integer, Integer> hashMap = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
    hashMap.put(nums[i], i);
}

for (int i = 0; i < nums.length; i++) {
    int num = nums[i];
    if (hashMap.containsKey(target-num) && hashMap.get(target-num) != i) {                
        return new int[]{hashMap.get(target-num), i};
    }
}

(출처: NeetCode)

HashMap을 써서 key값을 Integer 범위내로 저장할 수 있다

 

왜 생각이 안났을까..

자바 기본 클래스를 사용하지 않으려고 배열만 생각했던게 습관이 된 것 같다

map 자료구조는 배열을 쓰기 어렵구나..