[Leetcode 1] Two Sum - 4가지 방식의 풀이

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

Two Sum - LeetCode

 

Problem

덧셈하여 target을 만들 수 있는 배열의 두 숫자 인덱스를 리턴. 인덱스 값은 유일하게 존재한다.

 

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

출력 : [0, 1]

 

전략

문제는 매우 쉽다. 하지만 최적화할 수 있는 여러 가지 방법이 존재하여 중요한 문제라 생각한다.

 

풀이 1. 브루드 포스

 

시간복잡도 O(n²)

 public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

 

 

 

풀이 2.  HashMap을 활용

 

target 변수에서 첫 번째 수를 빼면 두 번째 수를 바로 알아낼 수 있다. 즉 수를 Map에 키로 등록하고, 그에 대응하는 인덱스를 값으로 등록하면 된다.

주의할 점은 검증을 할 때 같은 인덱스끼리 더하는 것은 허용되지 않기 때문에 그것도 제외를 해주는 로직이 들어가야 한다.

 

HashMap의 조회 시간 복잡도는 분할 상환 분석에 따라 O(1)이며 int[] nums를 한 바퀴 돌아야 하기 때문에 O(n)이다.

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

    for(int i = 0; i < nums.length; i++){
        numsMap.put(nums[i],i);
    }

    for(int i = 0; i < nums.length; i++){
        int num = nums[i];
        if(numsMap.containsKey(target-num) && numsMap.get(target-num) != i){
            return new int[]{i, numsMap.get(target-num)};
        }
    }
    return null;
}

 

 

 

 

풀이 3.  HashMap 활용(저장과 조회를 한번에)

 

이번 풀이는 위와 크게 달라진 점이 없다. Map 저장과 조회를 한 번에 하는 방식으로 변경했다. 동일하게 O(n)이며 미리 전체를 다 저장할 필요 없이 조회를 하며 하나씩 저장하는 방식이다.  실행속도는 이전 보다 for문이 줄었기 때문에 더 빠르고 코드도 간결해졌다.

 

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

    for(int i = 0; i < nums.length; i++){
        int num = nums[i];
        if(numsMap.containsKey(target-num)){
            return new int[]{numsMap.get(target-num),i};
        }
        numsMap.put(num,i);
    }
    return null;
}

 

 

 

 

 

풀이 4.  투 포인터 이용

target을 찾기 위해 왼쪽, 오른쪽 포인터를 조정한다. 코드를 보면 훨씬 직관적이다. 시간복잡도도 O(n) 이다. 하지만 이 문제는 오름차순으로 되있는 nums 배열을 제공하지 않는다. 그러면 정렬을 하면 되는 것 아닌가라고 생각할 수 있지만 인덱스를 반환해야 하는 문제라서 그것도 불가능하다. 

public int[] twoSum(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left != right) {
        if (nums[left] + nums[right] < target) {
            left += 1;
        } else if (nums[left] + nums[right] > target) {
            right -= 1;
        } else {
            return new int[]{left, right};
        }
    }
    return null;
}