투썸

Two sum은 leetcode의 첫 번째 질문 중 하나입니다. 이 문제를 어떻게 해결할 수 있는지 봅시다.

설명

정수 배열nums과 정수target가 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산되도록 합니다.

예 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

예 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

예 3:

Input: nums = [3,3], target = 6
Output: [0,1]

접근 방식 - 1: 무차별 대입

이제 무차별 대입 솔루션은 모든 쌍을 확인하여 합계가 대상인지 확인하고 그렇다면 해당 인덱스를 반환합니다. 이 접근 방식에 대한 코드를 확인해 보겠습니다.

// TC: O(n^2), SC: O(1)
public int[] twoSum_BruteForce(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[0];
}

for 루프를 중첩했기 때문에 이 접근 방식의 시간 복잡도는 O(n^2)이고 공간 복잡도는 추가 공간을 사용하지 않기 때문에 O(1)입니다.

⚠ 두 번째 for 루프에서 j = i + 1의 사용법에 유의하십시오. j = 0를 사용하여 동일한 코드를 가질 수도 있지만 i != j도 확인해야 합니다. 그렇지 않으면 추가하는 동안 동일한 숫자를 고려하게 됩니다.

접근 방식 - 2: 해시맵 사용

이전 접근 방식에서 i = 0 인 경우 전체 배열을 반복하지만 i = 1 인 경우 배열을 다시 반복합니다. 이것은 우리가 O(n^2)의 시간 복잡도를 가진 열악한 알고리즘을 갖도록 하기 전에 수행했던 중복되고 불필요한 작업입니다. 대신 내부 for 루프를 해시맵으로 바꿀 수 있다면 어떨까요?

즉, 배열을 반복할 때 보완 번호를 찾았는지 확인하도록 요청합니다. 필요한 목표는 10이고 현재 숫자는 6입니다. 그러면 필요한 보완 숫자는 6 + 4 = 10 이후 4입니다. 따라서 우리가 6에 있는 동안 보완 숫자가 이미 발견되었는지 묻고 그렇다면 인덱스를 가져와 현재 숫자의 인덱스도 반환할 수 있습니다. 그리고 보완 숫자를 찾는 방법은 단순히 대상에서 현재 숫자를 빼는 것입니다. 즉, complementary number = target - current .

이제 이에 대한 솔루션을 확인해 보겠습니다.

// TC: O(n), SC: O(n)
public int[] twoSum_HashMap(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};
        else map.put(nums[i], i);
    }
    return new int[2];
}

위의 솔루션은 단일 for 루프를 가지고 있기 때문에 O(n)의 시간 복잡도를 갖습니다. 그리고 최악의 경우 해시맵에 모든 숫자를 저장하고 마지막 줄인 return new int[2]에 도달하기 때문에 공간 복잡성도 O(n)이 됩니다.

접근 방식 3: 정렬 + 두 포인터 사용

정렬을 사용하는 또 다른 방법이 있습니다. 이 접근 방식은 Two Sum , Three Sum 등과 같이 Four Sum에서 파생된 문제를 해결할 때 매우 유용합니다.

첫 번째 단계는 배열을 정렬하는 것입니다. 두 번째 단계는 정렬된 배열의 가장 왼쪽 인덱스를 가리키는 포인터와 정렬된 배열의 가장 오른쪽 인덱스를 가리키는 포인터가 있는 두 개의 포인터를 갖는 것입니다.

그런 다음 이 두 포인터가 가리키는 값의 합을 확인하면 세 가지 경우가 있을 수 있습니다.

사례 1: 합계가 목표값과 같으면 답을 찾은 것입니다.

사례 2: 합계가 목표보다 작으면 방금 계산한 합계가 작으므로 이 합계를 늘려야 함을 의미합니다. 그리고 정렬된 배열에서 이 합계를 어떻게 늘리나요? 왼쪽 포인터를 오른쪽으로 움직이면 됩니다. 올바른 포인터가 아닌 이유는 무엇입니까? 이것은 정렬된 배열이며 오른쪽 포인터를 왼쪽으로 이동하면 이 합계가 감소한다는 것을 기억하십시오.

사례 3: 합계가 목표보다 크면 합계가 너무 커서 줄여야 함을 의미합니다. 그리고 케이스 2와 마찬가지로 합을 줄이기 위해 오른쪽 포인터를 왼쪽으로 이동합니다.

이제 이 접근 방식에 대한 코드를 확인하겠습니다.

// TC: O(nlogn), SC: O(n)
public int[] twoSum_Sort(int[] nums, int target) {
    List<Pair> pairs = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) pairs.add(new Pair(nums[i], i));

    pairs.sort(Comparator.comparingInt(a -> a.num));

    int i = 0, j = pairs.size() - 1;
    while (i < j) {
        int currentSum = pairs.get(i).num + pairs.get(j).num;
        if (currentSum == target) {
            return new int[]{pairs.get(i).index, pairs.get(j).index};
        } else if (currentSum < target) i++;
        else j--;
    }
    return new int[2];
}

static class Pair {
    int num, index;

    Pair(int num, int index) {
        this.num = num;
        this.index = index;
    }
}

위의 솔루션에 대한 시간 복잡도는 처음에 배열을 정렬하기 때문에 O(nlogn)입니다. 그 후 while 루프는 O(n)입니다. 추가 공간이 필요하지 않기 때문에 공간 복잡도는 O(1)입니다.