[LeetCode - Easy] 1. Two Sum

해석과 풀이는 개인적인 부분이기 때문에 참고만 하시길 바랍니다. 다른 접근 및 풀이는 언제나 환영합니다. 댓글로 남겨주세요.

 

1. 문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

 

2. 해석

숫자 배열[nums]이 주워지면 그 안에서 두 개의 숫자를 더해 목표[target]한 숫자가 나오도록 배열의 인덱스 몇번째와 몇번째가 필요한지를 구하는 문제이다.

 

3. 풀이

① 무차별 대입

- 단순하게 배열에서 하나씩 빼내어 더하면서 target 값이랑 동일한지 비교하는 접근방식으로 O(n^2) 시간 복잡도를 가진다.

- 아래는 leetCode에서 다른 사람의 풀이를 가져와 테스트하면서 주석만 달아봤다.

class Solution {
	
    public int[] twoSum(int[] nums, int target) {
    	
//    	int[] nums = {1,2,3,4,5,6};
        int n = nums.length;
        
        for (int i = 0; i < n - 1; i++) {
        	System.out.println("i = " + i);
        	
        	// i값이 증가함에 따라 안쪽 반복문의 j값의 시작값도 증가함으로 서로 중복을 피한다.
            for (int j = i + 1; j < n; j++) {
            	System.out.println("j = " + j + " => [" + nums[i] + ", " + nums[j] + "]");
            	
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        
        return new int[]{}; // No solution found
    }

- 필자도 단순하게 중첩 for문으로 처리했는데 배열에서 숫자를 꺼내면서 target과 감(-)하여 남은 숫자를 배열에서 찾는 방법을 사용했다.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];

        for(int i=0; i<nums.length; i++){
        	// 첫번째 index에서 가져온 값을 우선 target에서 빼본다.
            int rest = target - nums[i];

            for(int j=0; j<nums.length; j++){
            	// 위에서 빼서 남은 값이 배열에 있는지 찾아 비교한다.(단, 인덱스는 안겹치게)
                if (i != j && rest == nums[j]){
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }
        return result;
    }
}

② Hash Table을 이용

- 해시 테이블 조회에 평균적으로 일정한 시간이 걸리기 때문에 O(n)의 시간 복잡도를 갖는다.

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

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            //System.out.println(target + " - " + nums[i] + " = "+ complement);
            
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i};
            }
            numMap.put(nums[i], i);
            //numMap.forEach((key, value) -> System.out.println(key + " : " + value)); 
        }

        return new int[]{}; // No solution found
    }