Two Sum

Given an array of integers,

return indices of the two numbers

such that they add up to a specific target.

 

You may assume that each input would have exactly one solution,

and you may not use the same element twice.

 

예시)

int[] numbers = {1,1,3};
int target = 2;

int[] result = solution(numbers, target);

// [0, 1]
System.out.println(Arrays.toString(result));

풀이)

정수형 배열에 속하는 두 정수를 더해서 target과 같을 때, 두 정수가 위치한 배열의 인덱스를 정수형 배열로 반환하는 문제이다.

• 1 번째 시도 - 주어진 배열 전체를 HashMap에 넣고 나서, 검증 작업을 수행하였다. → for 문 하나와 이중for문이 생김. O(N^2)
• 2 번째 시도 - HashMap에 따로 넣지 않고, 이중 for문을 수행 → 여전히 O(N^2)

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

 

• 3 번째 시도 - 검증 후 HashMap에 저장 → O(N)

import java.util.Map;
import java.util.HashMap;

public int[] solution(int[] numbers, int target) {
  Map<Integer, Integer> indexToValue = new HashMap<>();
  for (int i = 0 ; i < numbers.length ; i++) {
    int key = target - numbers[i];
    if (indexToValue.contains(key) {
      return new int[]{indexToValue.get(key), i);
    }
    indexToValue.put(numbers[i], i);
    }
    throw new IllegelArgumentException();
}