[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.

인자 1: 정수 배열

인자 2(타겟): 정수

 

두 인자를 파라미터로 넘긴다. 정수 배열 안에 있는 값을 더해 타겟의 값을 만들 수 있는지 확인하고, 만들 수 있다면 해당되는 두 값의 인덱스 번호를 배열의 형태로 리턴한다.

 

조건 1: 각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있다. 동일한 요소를 두 번 사용할 수 없다.

조건 2: 순서에 상관 없이 답을 반환할 수 있다. 

예시) 

 

정답

---

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

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

    for (int i = 0; i < nums.length; i++) {
      int element = target - nums[i];
      if (numbersMap.containsKey(element)) {
        return new int[]{numbersMap.get(element), i};
      }
      numbersMap.put(nums[i], i);
    }
    return null;
  }
  }

 

1. 배열의 값과 인덱스 값을 넣을 용도로 Integer 타입을 키와 밸류로 가지는 맵을 생성한다. 

 

2. 여기서 잠깐 ‼️이 문제는 for문을 이중으로 돌려서 풀수도 있고 한번에 돌려서 풀수도 있다!! -> numberMap 안에 배열의 값과 인덱스 값을 넣는 for문과 타겟을 구하는 for문을 따로 둘수도 있고, 타겟을 구하면서 numberMap 안에 값을 넣어 한번에 처리할 수도 있다. 나는 효율성을 위해 한번에 처리했다.

 

3. arr이 {2, 7, 11, 15}, target이 9라고 가정하자. for문이 첫번째로 돌아갈 때 9-2=7 즉, element는 7이 된다. 

 

4. 만약 numberMap에 키 중에 7이 있다면 numberMap에서 해당하는 밸류 값을 가져온다. 현재 numberMap 안에는 값이 없는 상태이므로 가져올 것이 없으니 넘어간다.

 

5. numberMap 안에 값을 넣는다. nums[0]은 2, 그리고 인덱스 값은 0이므로 키: 2, 밸류: 0이 들어간다. 

 

6. for문이 두번째로 돌아간다. 9-7=2 즉, element는 2가 된다. 

 

7. numberMap 안에 키 2가 있는가? 있다. 그러면 조건문에 해당하니 배열을 만들어 반환하라는 명령이 실행된다. 배열 안에는 두개의 값이 들어간다. numbersMap.get(2)을 하면 나오는 값은 0, 그리고 현재 i는 1이니 1. 

 

8. [0,1]이 리턴된다.

 

이 문제의 핵심은!!  int element = target - nums[i] 바로 이부분.

배열에 있는 두 값을 더해 타겟을 만들 수 있는지 확인하려면 먼저 해당 값이 유효한 조합인지, 있는 값인지 확인하는게 먼저.

nums[i]는 우리가 확실히 가지고 있고, 알고 있는 값이다. target에서 nums[i]를 빼면, nums[i]와 어떤 숫자를 더해야 타겟 값이 나오는지 알 수 있게 된다.

그러니 numberMap의 키 중에 element 값이 없다면, 유효하지 않은 (배열에 있는 숫자로는 조합할 수 없는) 조합이라는 의미가 되어 조건문이 실행되지 않고 다음으로 넘어간다. 만약 numberMap 키로 element 값이 있다면 이는 유효한 조합이라는 의미가 된다.