[LeetCode#1] Two Sum

❒ Description

---

• 제목 : Two Sum
• 링크 : https://leetcode.com/problems/two-sum/description/
• 카테고리 : 선형 자료구조 중 배열 문제에 속한다.

주어진 배열 중 2개의 요소의 합이 target이 될 때, 각 요소의 index를 return하는 문제

 

 

 

❒ Solution

---

 

1. Brute Force

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

• 시간 복잡도 : O(n²)
• 모든 경우를 전부 확인하는 방법

---

 

2. Two-pass Hash Table

▶︎ Two-pass Hash Table
주로 두 번의 탐색을 통해 문제를 해결하는 알고리즘에서 사용되는 접근 방식이다.
이 기법은 특히 배열에서 특정 조건을 만족하는 두 요소를 찾는 문제에서 유용하다.
예를 들어, 배열에서 두 수의 합이 특정 값이 되는 두 요소를 찾는 문제에서 자주 사용된다.

public static int[] solve2(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++) {
        if (numsMap.containsKey(target - nums[i]) && i != numsMap.get(target - nums[i])) {
            return new int[]{i, numsMap.get(target-nums[i])};
        }
    }
    return new int[]{};
}

• 시간 복잡도 : O(n)
• Map 자료구조에 주어진 배열을 담고, 뺄샘으로 결과를 도출하는 방법

i != numsMap.get(target - nums[i])

위 코드가 필요한 이유는 이렇다. 예를 들어 배열이 [3,2,4] 이고 target이 6인 경우 numsMap.get(3)은

0이 되고, 이렇게 되면 [0,0]이 마치 정답인 것처럼 착각할 수 있기 때문에 넣은 코드이다.

 

---

3. One-pass Hash Table

public int[] solve3(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    int n = nums.length;

    for (int i = 0; i < n; i++) {
        int complement = target - nums[i];
        if (numMap.containsKey(complement)) {
            return new int[]{numMap.get(complement), i};
        }
        numMap.put(nums[i], i);
    }
    return new int[]{};
}

• 시간 복잡도 : O(n)
• 주어진 배열을 순회하면서 Map 자료구조에 배열의 요소를 담는 방식