1. Two Sum

문제출저

정수형 배열이 주어질때, 배열에 있는 두 원소의 값이 목표값(target)이 되는 인덱스쌍을 반환.
답은 정확히 하나이고, 같은 원소를 두번 사용할 수 없음.

예제

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

나의 풀이

2중 for문을 통해 정수형 배열에서 만들 수 있는 두개의 정수쌍(pair)을 통해 합이 target 값과 일치하는것이 있는지 찾는다.
배열의 크기가 n이라고 할때 O(n^2)의 시간복잡도가 나오게 된다.
이 문제에서는 배열의 크기에 대한 제약이 없는데, 만약에 배열의 크기가 매우 크면 시간초과가 날수있을 것이다.

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

        for (int i = 0, n = nums.length; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null;
    }

Leetcode Article

참조

접근법 1.Brute Force

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[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

내가 풀었던 접근법과 동일하다. 다만, 마지막에 값이 없을 경우 IllegalArugmentException으로 처리해주었다.
IllegalArgumentException은 입력값(인자값)이 부적합할 경우 발생되는 예외이다.

복잡도 분석

  • 시간복잡도(Time Complexity) : O(n^2)
  • 공간복잡도(Space Complexity) : O(1)

접근법 2. Two-pass Hash Table

위의 Brute Force방식에서 현재 값(num[i])이 target이 되기 위해서는 현재값과 쌍을 이루는 값이 주어진 배열에 있는 값이라는것에 주목하자. (또한, 이 쌍을 이루는 값은 num[i]가 될수없다.)
베열의 각 요소를 인덱스에 매핑하는 방법으로 Hash Table을 이용해보자.

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];
        // 현재 수(nums[i])와 쌍을 이루는 값이 map에 존재하는지 체크
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[] { i, map.get(complement) };
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

복잡도 분석

  • 시간복잡도(Time Complexity) : O(n)
    우리는 n개의 원소들을 정확히 두번 순회한다. 그리고 HashTable은 찾는 시간을 O(1)로 단축시켜주기 때문에, 시간 복잡도는 O(n)이 된다.
  • 공간복잡도(Space Complexity) : O(n)
    해시테이블을 구성하기 위한 추가적인 공간이 요구되고, 그것은 입력으로 주어진 원소들의 개수에 따라 달라진다.

접근법 3. One-pass Hash Table

접근법2에서는 배열의 각요소에 대한 인덱스값을 사전에 저장하는 방법을 취했다. 하지만 이번에는 우선, 현재 값과 쌍을 이루는 값(complement)이 map에 존재하는지 안하는지 체크하는 방식을 취한다.
존재하지 않는다면, 현재값을 map에 넣어두고, 다음단계를 진행하면 된다.

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);
    }
    throw new IllegalArgumentException("No two sum solution");
}

복잡도 분석

  • 시간복잡도(Time Complexity) : O(n)
    우리는 n개의 원소들을 단지 1번만 순회한다. hash table에서 해당값을 찾는 시간복잡도는 O(1)이다.
  • 공간복잡도(Space Complexity) : O(n)
    해시테이블을 구성하기 위한 추가적인 공간이 요구되고, 그것은 입력으로 주어진 원소들의 개수에 따라 달라진다.