[알고리즘] #Two Sum

출처: LeetCode https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

(정수로 이루어진 array가 주어졌을 때, 두 숫자의 index의 합이 target과 같은 경우의 index를 리턴하는 function을 구하세요.)

 

Example:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

 

 

 

---

#1. for 문을 이용해 [0,1], [0,2] ... [nums.length-2, nums.length-1] 까지 비교해보는 방법

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indices = new int[2];
        
        for(int i=0; i<nums.length-1; i++) {
            for(int j=i+1; j<nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    indices[0] = i;
                    indices[1] = j;
                    return indices;
                }
            }
        }
        return indices;
    }
}

>>>> 결과 : Success. 하지만 Runtime 시간과 메모리 사용량을 더 줄일 수 있는 방법을 찾아보는게 좋겠다. 

 

Runtime 시간 분포도

 

메모리 사용 분포도

 

 

 

 

---

#2. HashMap을 이용한 방법

key에는 정수배열 값을, value에는 index 값을 담은 HashMap을 만들어서 비교하는 방법이다.

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

>>>> 결과 : Success. Runtime 시간이 첫번째 방법보다 훨씬 줄었다. 그런데 코드를 보면 같은 범위의 for문이 2번 돈다. 하나의 for문으로 합쳐주면 아래와 같다.

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

 

Runtime 시간 분포도

 

메모리 사용량 분포도