[Leetcode] Two Sum - java

https://leetcode.com/problems/two-sum/

문제 파악

숫자 배열이 주어지고 배열에서 두 수의 합이 target이 되는 숫자들의 인덱스를 구하는 문제

---

접근 방법

1. 반복문으로 하나씩 처리
2. 메모이제이션

나는 메모이제이션으로 처리함.

• 해시테이블에 숫자와 타겟에서 숫자를 뺀 값을 저장
• 반복문에서 nums[i]가 해시테이블의 값에 들어가있으면 인덱스 반환
• → 문제점… 해시테이블 안의 숫자의 인덱스를 구할 방법이 없음

해결방안

1. 숫자와 인덱스를 해시테이블에 저장
2. 필요한 숫자가 해시테이블의 key 에 저장되어있으면 해당 value = 인덱스 정보를 호출
3. 해당 인덱스와 현재 인덱스를 배열로 반환

---

코드 구현

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> memo = new HashMap<>();
        for(int i= 0; i < nums.length; i++){
            // target에서 숫자를 빼서 필요한 숫자를 계산
            int needed = target - nums[i];

            // 필요한 숫자가 해시테이블에 저장되어있으면
            if(memo.containsKey(needed)){
                return new int[] {memo.get(needed), i}; // 해당 숫자의 인덱스 정보와 현재 인덱스 반환
            }
            memo.put(nums[i], i);   // num과 인덱스를 저장
        }
        return new int[] {-1, -1};
    }
}

---

배운 점

메모이제이션 방법을 다시 상기시킬 수 있었다.
코테를 잠시 놓으니까 모든 지식이 초기화됐다... 비상..
얼른 다시 감을 찾아야 할 것 같다.