LeetCode 1(Two Sum, java)

0. 문제

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

Two Sum - LeetCode

 

1. 문제 설명 및 해결 전략

- 문제에서 배열(nums)과 찾는 값(target)이 주어진다.

- 이 문제의 핵심은 주어진 배열의 요소 2개를 더하여 target을 만들 수 있느냐는 것이다.

- 주어진 배열의 요소 2개를 더하여 target을 만들 수 있다면 두 요소의 index를 배열에 담아 결과로 반환한다.

- 모든 문제의 전제 조건으로, target을 만드는 단 하나의 조합이 존재한다. 

 

- 이 문제를 해결하기 위해서는 기본적인 일차 방정식을 필요로 한다. 

 

- for문을 이용하여 배열의 요소를 순차적으로 탐색하면서 하나의 요소를 선택한다.

- 그다음에는 (target - 선택된 요소)를 계산하여 연산 결과가 배열에 존재하는지 파악한다.

 

- 이때 2가지 고려사항이 발생한다.

   → 연산 결과를 찾기 위해서 for문으로 배열을 탐색하면 선택된 요소를 제외하고 탐색해야 한다는 문제가 발생한다.

   → 연산 결과를 찾기 위해서 for문으로 배열을 탐색하면 이중 for문으로 시간복잡도가 O(n^2)로 증가한다. 

 

- 이 2가지 고려사항을 해소하기 위해서 HashMap을 사용한다.

 

2. 정답 코드

class Solution {

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

        for(int i = 0; i < nums.length; i++) { // 배열을 순차적으로 탐색
            
            int requiredNum = target - nums[i]; // 연산 결과
            
            // 연산 결과가 map에 존재하는 경우
            // ==> map에 존재하는 요소는 이미 지나간 요소이므로 동일한 요소를 선택하는 문제를 해소
            if(map.containsKey(requiredNum)) { 
                int result[] = {map.get(requiredNum), i}; // 각 요소의 index를 배열에 저장
                return result; // 결과 반환
            }
            
            map.put(nums[i], i); // 연산 결과가 map에 없다면, 해당 요소를 map에 저장
        }
        return null; // 어떠한 조합도 없는 경우
    }
}