🔎 알고리즘-Leetcode 두 개의 합 (Two Sum) java

📌 문제

n개의 정수 배열이 주어졌을 때 배열의 두 개 원소의 합으로 target 값을 만족하는 두 개 원소의 인덱스를 구하여라.
(시간복잡도 O(N) 제한)

📌 풀이

시간복잡도가 O(N)으로 제한되었기 때문에 두 개 for문으로 두 개 원소의 모든 조합을 보는 것은 불가능합니다.

한 개의 for문으로 풀어내기 위해 Map을 사용하였습니다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
        Map<Integer, Integer> map = new HashMap<>();        
        for (int i=0;i<nums.length;i++) {
            if (!map.containsKey(nums[i])) {
                map.put(target-nums[i], i);
            } else {
                return new int[]{map.get(nums[i]), i};
            }
        }
        return new int[] {0,0}; 
    }
}

Map에 저장되는 key값은 target에서 배열의 i번째 값을 뺀 값을 저장

만약 Map의 키 값과 같은 배열의 원소가 들어온다면 그 두 개 원소의 합이 target인 것.
(Map의 key값은 이미 해당하는 인덱스 번째 값을 뺀 값이기 때문)