[LeetCode] Two Sum

---

배열과 target을 파라미터로 받아서 배열 중 두 개의 숫자가 target과 같으면 그 숫자들의 인덱스 번호를 출력하는 문제다!

나는 for문을 사용해서 문제를 풀었는데 이렇게 되면 정답은 나오지만 시간복잡도가 O(n2) 가 되어서 매우 비효율적이라고 한다 🤔🤔 (Follow-up에서도 O(n2)보다 작은 알고리즘을 생각할 수 있냐고 물으니까... 원하는 답은 아닌 듯하다!)

class Solution {
    public int[] twoSum(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 null;
    }
}

참고로 내가 문제 풀이에 사용한 이 방식은 brute force 라고 부르는데 직역하니까 무식한 힘 이라고 한다...... 😂 껄껄껄 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가지고 온다고......

---

그래서 시간복잡도가 O(n) 이 될 수 있는 방법에 대해서 생각을 해봤지만... 자바에 대한 이해도, 숙련도가 모두 떨어지다보니 (더 공부하자...) 검색해볼 수 밖에 없었다... Hasp Map을 사용하는 방법이 대부분이었고 그 중에서 Two-pass Hash Table, One-pass Hash Table 가 흥미로워서 공부해보기로 했다.

Map, List은 찍먹으로 훑어보기만 했는데(코로나 때문에 자가격리 하는 동안에 수업해서 ㅠㅠ) 요즘 실습하다보니 진짜 자주 사용하는 것 같아서 제대로 다시 공부를 해야겠다고 다짐...🙄

---

LeetCode에서 압도적으로 좋아요(?)가 많이 눌린 문제 풀이글이다! >❤<

Approach using a hash table:

1. Create an empty hash table to store elements and their indices.
2. Iterate through the array from left to right.
3. For each element nums[i], calculate the complement by subtracting it from the target: complement = target - nums[i].
4. Check if the complement exists in the hash table. If it does, we have found a solution.
5. If the complement does not exist in the hash table, add the current element nums[i] to the hash table with its index as the value.
6. Repeat steps 3-5 until we find a solution or reach the end of the array.
7. If no solution is found, return an empty array or an appropriate indicator.

This approach has a time complexity of O(n) since hash table lookups take constant time on average. It allows us to solve the Two Sum problem efficiently by making just one pass through the array.

• 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
    }
}

if (numMap.containsKey(complement) && numMap.get(complement) != i
=> numMap에 complement라는 키값이 있거나(&&) numMap의 complement가 i와 같지않으면

이 부분이 처음에 이해가 잘 안됐는데 문제에서 You may assume that each input world have exactly one solution, and you may not use the same element twice. 때문에 numMap.get(complement) != i 라는 조건이 추가된거다!

---

One-pass는 뭐가 다른가 했더니 위에서 궁금했던 numMap.get(complement) != i 조건이 없는 버전이었다. 둘 다 실행에는 문제가 없지만 더 확실하게 문제에서 요구하던 답은 two-pass가 맞는 것 같다!

• 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
    }
}