Two Sum문제 풀이

문제

Problem_Link

내 답

• 1시간 제한
• 인터넷 사용 안함

Overview

• input : int[] nums, int target
• output : int[]

My code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int temp[] = new int[nums.length];
        int rtn[] = new int[2];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = target - nums[i];
            for (int j = 0; j < i; j++) {

                if (temp[j] == nums[i]) {
                    rtn[0] = j;
                    rtn[1] = i;
                    return rtn;
                }
            }
        }
        rtn[0] = 0;
        rtn[1] = 0;
        return rtn;
    }
}

• Time complexity: $O(n^2)$
• Space complexity $O(1)$

---

최선의 답

인터넷과 책에서 찾아본 답

class Solution {
    public int[] twoSum(int[] nums, int target) {

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

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

            if (map.containsKey(tempkey)) {
                return new int[] { map.get(tempkey), i };
            }

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

        throw new IllegalArgumentException("No solution");
    }
}

• Time complexity: $O(n)$
• Space complexity $O(n)$

반성 할 점

• Brute Force 방법으로 문제를 풀었다. 이 방법 자체가 틀린것은 아니지만 매우 비효율적인 답이였다. 효율적인 방법을 찾는 연습이 필요함.

필요한 공부

• IllegalArgumentException (exceptions)
• hash