[LeetCode] - 1. Two Sum

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Two Sum" 문제입니다.

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

 

문제 : 

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 : nums[0] + nums[1] == 9, so we return [0, 1].

Example 2:

• Input : nums = [3, 2, 4], target = 6
• Output : [1, 2]
• Explanation : nums[1] + nums[2] == 6, so we return [1, 2].

Example 3:

• Input : nums = [3, 3], target = 6
• Output : [0, 1]
• Explanation : nums[0] + nums[1] == 6, so we return [0, 1].

Constraints : 

$2 \leq \text{nums.length} \leq 10^4$ 

$-10^9 \leq \text{nums}[i] \leq 10^9$ 

$-10^9 \leq \text{target} \leq 10^9$

 

Follow-up : Can you come up with an algorithm that is less than \(O(n^2)\) time complexity?

---

해당 문제는 정수 배열 nums와 정수 target이 주어졌을 때, 두 수의 합이 target이 되도록 하는 두 숫자의 인덱스를 반환하는 코드를 쓰라고 요구합니다.

각 입력에는 정확히 하나의 설루션이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없습니다.

인덱스를 반환하는 순서는 상관없습니다.

이 문제도 여러 접근 방식이 있습니다. 저는 사실 Brute Force 밖에 생각 못해냈는데, 다른 유저들의 설루션을 보고,

One / Two pass Hash Table solutions을 이해하게 됐습니다. 코드를 보시죠 : 

 

1. Brute Force (무차별 대입) : 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        return res;
    }
}

 

 

위 코드를 간략히 설명하자면 이렇습니다 : 

• 결과 배열 초기화 : 길이가 2인 정수 배열 res를 초기화합니다.
• 이중 for 루프 : 두 개의 for 루프로 배열의 모든 가능한 쌍을 순회합니다.
• 합 확인 : 두 숫자의 합이 target과 같은지 확인합니다.
• 인덱스 저장 : 합이 target인 경우, 두 숫자의 인덱스를 res 배열에 저장합니다.
• 결과 반환 : res 배열을 반환합니다. 

말 그대로 그냥 모든 경우의 수를 도전하는 것입니다. 제목대로, 이 코드는 매우 심플하고 1차원적이며, 그렇기에 시간복잡도는 높습니다 ( \(O(n^2)\) ). 그래서 뒤에 나오는 코드들이 더 Optimized 된 코드들일 겁니다.

---

2. One pass Hash Table : 

class Solution {
    public int[] twoSum(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[]{}; // No solution found
    }
}
//rahulvarma5297 유저의 코드

 

이 코드를 간략히 말하자면, 배열을 한 번 순회하면서 각 원소에 대해 보완 수를 계산하고, 해시맵을 사용하여 보완 수가 이미 배열에 존재하는지 효율적으로 확인합니다. 시간 복잡도는 O(n)으로, 무차별 대입 방법보다 훨씬 효율적입니다.

 

보완수란 무엇이냐? ==> 보완수는 특정 목푯 값(target)에서 현재 값(nums[i])을 뺀 값을 의미합니다. 즉, 두 수의 합이 target이 되도록 하는 두 번째 수를 말합니다.

 

예를 들자면, 

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

코드의 흐름을 따라가면 다음과 같습니다:

1. 초기 상태:
   • 해시맵: {}
2. 첫 번째 반복 (i=0):
   • 현재 숫자: nums[0] = 2
   • 보완수: complement = target - nums[0] = 9 - 2 = 7
   • 해시맵에 7이 있는지 확인: 없음
   • 해시맵 업데이트: {2: 0}
3. 두 번째 반복 (i=1):
   • 현재 숫자: nums[1] = 7
   • 보완수: complement = target - nums[1] = 9 - 7 = 2
   • 해시맵에 2가 있는지 확인: 있음 (인덱스 0)
   • 따라서, nums[0] + nums[1] = 2 + 7 = 9가 되어 target과 같아집니다.
   • 정답을 찾았으므로 [0, 1]을 반환합니다.

 

이런 식으로 해시맵을 이용해서 찾아가는 겁니다.

---

3. Two Pass Hash Table :

 

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

        // Build the hash table
        for (int i = 0; i < n; i++) {
            numMap.put(nums[i], i);
        }

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

        return new int[]{}; // No solution found
    }
}
// rahulvarma5297 유저의 코드

 

 

위 코드가 어떻게 작동하는지 요약해서 설명하자면, 두 번의 for 루프를 사용하여 배열 nums의 값을 해시맵에 저장한 후, 각 값에 대한 보완수를 해시맵에서 검색하여 두 수의 합이 target이 되는 인덱스를 찾습니다.

이 방법은 시간 복잡도가 O(n)으로 효율적입니다.

첫 번째 루프는 해시맵을 구축하고, 두 번째 루프는 보완수를 검색합니다.

이를 통해 두 수의 합이 target이 되는 두 수의 인덱스를 효율적으로 찾을 수 있습니다.

 

제일 중요한 부분은 역시 보완수를 찾는 코드인데, 더 파해쳐 보자면 이런 로직입니다 : 

• 두 번째 for 루프 (for (int i = 0; i < n; i++))는 배열 nums의 각 원소를 다시 순회합니다.
• int complement = target - nums[i];를 통해 현재 원소 nums [i]의 보완수를 계산합니다.
• if (numMap.containsKey(complement) && numMap.get(complement)!= i) 조건문은 해시맵에 보완수가 존재하며, 그 보완수의 인덱스가 현재 인덱스 i와 다른지 확인합니다.
  • numMap.containsKey(complement): 해시맵에 보완수가 키로 존재하는지 확인합니다.
  • numMap.get(complement) != i: 보완수의 인덱스가 현재 인덱스와 다른지 확인합니다. 이는 동일한 요소를 두 번 사용할 수 없기 때문입니다.
• 조건이 참이면, return new int[]{i, numMap.get(complement)}; 를 통해 현재 인덱스 i와 보완수의 인덱스를 반환합니다.

---

1,2,3 순서대로의 Runtime 결과