[LeetCode] 1. Two Sum - Java

Two Sum - LeetCode

 

문제

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]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 

정수 target 과 정수 배열 nums 가 주어졌을 때 배열 요소 두개의 합이 target과 일치할 경우 해당 요소의 인덱스로 이루어진 배열을 반하는 문제이다.

 

---

 

내 풀이

 

첫 번째 풀이 - 전체 탐색

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

일단 가장 간단한 방법

무지성 for문 돌리기…! 내가 썼지만 어마어마한 들여쓰기에 벌써 어지럽다.

 

• 시간 복잡도 : O(n^2)
• 공간복잡도는 : O(1)

 

당연히 효율적인 방법이 아니다. 다음 풀이를 보자.

 

 

두 번째 풀이 - HashMap 사용

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

        int[] answer = new int[2];
        Map<Integer, Integer> map = new HashMap<>();

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

        for(int i = 0; i<nums.length; i++){
            int diff = target - nums[i];
            int index = map.getOrDefault(diff ,-1);

            if(index != -1 && index != i){
                answer = new int[]{i, map.get(diff)} ;
                break;
            }
        }
        return answer;
    }
}

해시 맵을 사용해서 풀었다.

nums 배열을 반복하며 각 숫자를 맵에 key로, 해당 인덱스를 value로 추가한다.

그 후 nums 를 다시 순회하면서 diff = target - nums[i] 가 맵에 존재하는지 검사한다.

이 과정에서 찾은 인덱스가 현재 인덱스 i와 다른지 확인하여 동일한 요소가 두 번 사용되지 않도록 한다.

일치하는 값이 발견되면 인덱스 쌍을 answer 배열에 추가하고 반복문을 종료한다.

 

• 시간복잡도 : O(n) - 배열 순회
• 공간복집도 : O(n) - 배열의 각 요소를 저장하는 해시 맵

 

해시 맵을 사용해서 반복문을 1번만 돌며 시간복잡도를 O(n)으로 줄일 수 있었다.