Problem

---

https://leetcode.com/problems/two-sum/?envType=problem-list-v2&envId=rab78cw1

Grind 75의 Easy 문제다.

Solution

---

문제에서 말하기를

• 무조건 배열 내 정답이 있다. -> 따라서 return문을 마지막에 return null로.
• 배열 내 같은 요소는 2번 사용될 수 없다.

Code

---

가장 중요한 것은 방식이 아니라 정답에 어떻게든 도달하는 것이다.

• 이중 for문으로 brute force 탐색을 진행한다.

• HashMap으로 O(n) 성능으로 최적화한다.

  • target - nums[i] 를 키 값으로 해서 조회했을 때 map에서 null이 아니면?
    • map에서 조회한 인덱스와 i를 반환하면 된다.
  • null이면 현재의 값을 맵에 넣고 끝.

체크리스트
1. map.get(key)를 할 때 이중으로 조회하면 틀린다. -> value가 null인가?를 두고 비교한다.
2. 배열 내 같은 요소를 2번 사용할 수는 없다. brute force, hashMap 모두 요소의 중복 사용하지 않도록 짜야 한다.

Brute Force

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    return new int[]{i,j};
                }
            }
        }
        return null;
    }
}

HashMap (최적화)

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

        map.put(nums[0], 0);

        for(int i = 1; i < nums.length; i++) {
            Integer value = map.get(target - nums[i]);

            if(value == null) {
                map.put(nums[i], i);
            } else {
                return new int[]{ value, i};
            }
        }
        return null;
    }
}