[LeetCode/EASY] 1. TwoSum (JAVA) : 문제&풀이

 

int배열에서 두 수의 합이 target일 때,

이 두 수의 index를 배열로 반환하는 문제이다.

e.g. {1, 4, 7, 8}, 11 → 4 + 7 = 11 → {1, 2}

 

int배열과 단일 int를 매개변수로 받는 twoSum 메서드의 틀이 주어진다.

 

Problem :

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {

    }
}

풀이는 주어진 twoSum 메서드에 작성하면 된다.

 

Solution1 :

매우 간단한 방법으로 이중 for문을 이용해 다음과 같이 풀 수 있다.

(반목문을 통해 두 수의 합이 target과 일치하는지 확인하는 방법)

public class TwoSum {
    // time complexity : for double loop -> O(n^2)
    // space complexity : no extra space allocated -> O(1)
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length -1; i++){
            for(int j = i+1; j < nums.length; j++){
                if(nums[i] + nums[j] == target)
                    return new int[]{i, j};
            }
        }

        return new int[]{};
    }
}

 

Complexity1 : 

• 시간복잡도 (Time Complexity)
  • 이중 for문 사용에 따라 O(n²)
• 공간복잡도 (Space Complexity)
  • 추가 할당하여 사용하는 공간이 없으므로 O(1)

 

Solution2 :

보수와 Map의 containsKey() 메서드를 이용한 풀이는 다음과 같다.

1. 현재 index를 value로 하고 해당 보수값을 key로 하는 Map을 선언한다.
2. 반복문을 돌며 Map에 현재 수(nums[i])의 보수가 있는지 확인한다.
   1. 있는 경우, 현재수를 보수로 갖던 수의 index와 현재 index를 int배열을 생성하여 반환한다.
   2. 없는 경우, 현재 수의 index를 value로 하고 현재 수의 보수값을 key로 하는 데이터를 삽입한다.
3. 주어진 int배열의 조합으로 target을 만들 수 없는 경우, 빈 배열을 반환한다.

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    // time complexity : for loop -> O(n)
    // space complexity : HashMap to push number of 'int[] nums' -> O(n)
    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])){
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }

        return new int[]{};
    }
}

 

Complexity2 : 

• 시간복잡도 (Time Complexity)
  • for문 사용에 따라 O(n)
• 공간복잡도 (Space Complexity)
  • 주어진 배열의 항목 수만큼 HashMap에 저장하므로 O(n)

 

첫번째 방법 경우 시간복잡도(time complexity)가 제곱이 되기 때문에 두 번째 방법을 권장한다.

 

Sample(Test) :

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    // time complexity : for loop -> O(n)
    // space complexity : HashMap to push number of 'int[] nums' -> O(n)
    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])){
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }

        return new int[]{};
    }

    public static void main(String[] args) {
        int[] nums = {1, 4, 7, 8};
        int target = 11;

        TwoSum t = new TwoSum();
        System.out.println(Arrays.toString(t.twoSum(nums, target)));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

[2, 3]