[LeetCode] 1. Two Sum (Java 문제풀이)

문제링크: https://leetcode.com/problems/two-sum/

Problem

주어진 문제는 주어진 배열의 두 숫자를 골라 더했을 때 target이 되는 숫자들의 index를 구하는 문제이다.

Solution

먼저 HashMap에 숫자를 key, index를 value로 집어넣는다.

이 때 중복값이 허용되므로 같은 숫자가 존재할 경우에 가장 마지막 숫자의 index가 value로 들어간다.

 

예) 숫자배열이 num: [1, 3, 5, 5, 8], target: 10이라고 한다면

생성된 HashMap은 {1:0, 3:1, 5:3, 8:4}이런 모양새가 된다.

이제 다시 숫자배열을 0번 index 부터 돌면서 target - num[index] 의 값이 생성한 HashMap의 key에 존재하는지 확인한다.

1. index 0, num[0]: target - num[0] == 10 - 1 == 9. 9는 HashMap의 key 에 존재하지 않아서 pass.
2. index 1, num[1]: target - num[1] == 10 - 3 == 7. 7은 HashMap의 key 에 존재하지 않아서 pass.
3. index 2, num[2]: target - num[2] == 10 - 5 == 5. 5는 HashMap의 key 에 존재한다. key:5 value:3

즉 정답이 되는 두 index는 2와 3이다.

정답: [2, 3]

정답코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        final var map = new HashMap<Integer, Integer>();
        for (int i = 0 ; i < nums.length; i++) {
            map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            final var exactNumber = target - nums[i];
            if (map.containsKey(exactNumber) && map.get(exactNumber) != i) {
                return new int[]{i, map.get(exactNumber)};
            }
        }
        return new int[]{0, 0};
    }
}

ps. 이번처럼 정답이 5, 5인 경우? index는 늘 0부터 커지는 방향으로 움직이고, HashMap에 저장될 때 key값이 중복될 경우 가장 마지막의 index값이 value로 저장된다. 그러므로 for문의 i 값이 먼저, HashMap의 value 값이 뒤에오게 제출하면 된다.