class Solution {
    
    // 두 숫자가 타겟에 합산되도록 인덱스를 반환
    // O(n)
    public int[] twoSum(int[] nums, int target) {
        int[] output = new int[2];
        
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 보수값(complement)을 맵에서 검색해서 존재하면 
            Integer c = map.get(target - nums[i]);
            if (c != null) {
                output[0] = i; // 현재 인덱스
                output[1] = c; // 보수값의 인덱스
                break;
            // 존재하지 않으면 맵에 현재값과 인덱스를 넣는다
            } else {
                // 키: 숫자, 값: 인덱스
                map.put(nums[i], i);
            }
        }
        
        return output;
    }
}