문제

https://leetcode.com/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법

• 2중 for문을 돌려 각각 더해서 target이 나오는지 체크하면 간단하게 해결할 수 있지만, 문제에서 O(n^2)보다 빠르게 해결하라고 함
• 숫자 2개의 합만 구하면 되기 때문에, x가 주어졌을 때 target - x가 존재하는지만 체크하면 됨
• 체크 배열을 사용하려 했지만, nums[i]의 범위가 -10^9 ~ 10^9이므로 배열을 사용하는데는 무리가 있음
• 따라서 HashMap을 사용하기로 함
• HashMap의 Key 값으로 nums[i]를 저장, Value 값으로 i를 저장하고, 다음 nums[j]에서 Key 값으로 target - nums[j]가 존재하는지만 체크해주면 됨
  • target - nums[j]가 존재하지 않으면 (nums[j], j)를 HashMap에 삽입
  • target - nums[j]가 존재한다면 HashMap에 Key가 (target - nums[j])인 value와 j를 answer에 담아 return

코드

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  ++) {
            if (map.containsKey(target - nums[i])) {
                answer[0] = map.get(target - nums[i]);
                answer[1] = i;
                break;
            }

            if (!map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
        }

        return answer;
    }
}

결과