[LeetCode] (Easy) Two Sum **

문제

---

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

 

You may assume that each input would have exactly one solution, and you may not use the same element twice.

 

You can return the answer in any order.

 

Example 1:

 

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

Example 2:

 

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

 

Example 3:

 

Input: nums = [3,3], target = 6
Output: [0,1]

 

정답 코드

---

<  내 정답 코드  >

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];

        outer:
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    answer[0] = i;
                    answer[1] = j;
                    break outer;
                }
            }
        }

        return answer;
    }
}

 

<  타인 답변 코드  >

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] answer = new int[2];

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                answer[0] = i;
                answer[1] = map.get(target - nums[i]);
                break;
            }

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

        return answer;
    }
}

이것을 주의하자!

---

-  쉽게 생각하면 이중 for문을 돌리면서 모든 원소를 하나씩 비교하는 방법이 있다. 가장 기본적인 방법! 하지만 시간 복잡도를 생각하면 이중 for문이기 때문에 O(n²) 이 된다. 원소가 늘어나면 부담이 되는 알고리즘이다.

 

-  타인 작성 코드를 보면 HashMap 을 이용했다. 즉 배열을 한 번만 탐색하면 되기 때문에 O(n)이 된다. 배열의 원소값을 'key' 로, 해당 원소의 인덱스를 'value' 로 map에 저장한다. 그리고 구하고자 하는 값인 target 에서 다음 배열의 원소를 뺀 값, 다시 말해 두 수의 차가 map 에 이미 저장되어 있으면 해당 키의 value 값을 가져 나오면 된다.

 

-  쉽다고 얕보면 안 된다. 항상 시간 복잡도 측면에서 효율적인 코드가 무엇인지 고민해보자!