[LeetCode] 1. 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]
Output: 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]

배열안에서 target 값과 같아지는 두개의 값의 인덱스를 출력하는 문제

풀기 전에 생각 한 순서

1. 기준이 되는 값을 정하고
2. 다른 값과 계속해서 더한다음에
3. target 값이 나오는 순간 출력하자

결국 한가지 값을 기준으로 다른 하나의 값을 계속 비교해야하니 이중포문을 사용하면 가능할 것같았다.

그렇게 해서 첫번째로 구현하게 된 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int [] output = new int[2]; // output 배열 생성
        for(int i =0; i<nums.length; i++){ //첫번째 값
            for(int j = i + 1; j<nums.length; j++){ //비교할 값
                if(nums[i] + nums[j] == target && i != j){ // 같은 인덱스가 아니면서 target이 되는 i,j구하여 output에 넣어주기
                    output[0] = i;
                    output[1] = j;

                }
            }
        }

        return output;
    }
}

Runtime	Memory
11 ms	40.6 MB

이렇게 구현 할 경우 시간복잡도가 O(n^2)가 되기 때문에 오래 걸린다.

O(n)으로 줄이기 위해 for문을 한번만 돌릴 수 있는 방안을 고민했지만 생각해내지 못했고

Discussion에서 최적화된 방법을 발견했다.

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

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

            if (prevMap.containsKey(diff)) {
                return new int[]{ prevMap.get(diff), i };
            }
            prevMap.put(nums[i], i);
        }
        return new int[0]; // Guranteed solution, no need for return
    }
}

이 알고리즘의 핵심은 한 가지 값을 기준으로 target에서 그 값을 뺀 나머지 수가 배열에 포함되어있는지를 확인하는 것이 핵심이다.

• 내가 생각하지 못했던 것

1. target에서 특정 값을 뺀 뒤 비교하는것
2. Map을 사용하는것

사용한 메소드

map.containskey(key) : key값이 map에 있는지 확인 // return값 boolean

map.get(key) : key를사용하여 value값 출력

for문 작동 순서 (num[] = {3, 2, 4} / target = 6 인 경우)

i = 0 일 때
diff = 3
prevMap에 (3,0) 추가

i = 1 일 때
diff = 4
prevMap 에 (2,1) 추가

i = 2 일 때
diff = 2
containsKey(2) = true
get(2) = 1
최종적으로 {prevMap.get(2) = 1 , i = 2}
{1,2} 출력