[LeetCode] 1. Two Sum - 문제풀이

Description

주어진 배열 요소 두개의 합이 target과 일치할 경우 해당 요소의 인덱스로 이루어진 배열을 반하는 문제입니다.

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]

Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than O(n2) time complexity?

Solution 1. List 길이 체크

public int[] twoSum(int[] nums, int target) {
    //1. brute force
    int len = nums.length;
    for (int i = 0; i < len-1; i++) {
        for (int j = i+1; j < len; j++) {
            if(nums[i]+nums[j] == target){
                return new int[]{i,j};
            }
        }
    }
    return null;
}

전체 탐색을 통해 처음으로 tartget과 일치하는 요소가 나올 경우 해당 인덱스를 반환하는 로직입니다.

• 시간 복잡도 : O(N^2)
• 공간 복잡도 : O(1)

Solution 2. Map 사용

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

Map을 이용하여 각각 배열의 요소를 key로 하여 index위치를 기억해 놓고 target과의 차이를 계산하여 해당값으로 맵에 데이터가 있으면 인덱스를 반환합니다.

• 시간 복잡도 : O(N)
• 공간 복잡도 : O(N)

Reference

Two Sum - LeetCode