[알고리즘] LeetCode - Two Sum

Two Sum - LeetCode

문제 설명

• 정수형 배열 nums가 주어진다.
• 두 숫자의 합인 정수형 변수 target이 주어진다.
• nums안의 두 숫자를 더해 target되는 경우에 두 수의 인덱스를 정수형 배열 형태로 반환한다.
• 정답 배열은 어떤 순서든 상관없다.
• 각 테스트 케이스에는 정확히 하나의 정답인 경우가 존재한다.
• 동일한 요소를 두 번 사용할 수 없다.

문제 해결

• 값을 Key로 인덱스를 Value로 하는 HashMap을 선언해서 값들을 저장한다.
• target에서 현재 자리의 수를 뺀 값이 HashMap에 존재하면 현재 수와 HashMap안에 있는 수의 합이 target이 되는 경우이므로 인덱스를 반환한다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int N = nums.length;
        
        int[] answer = {};
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            if (map.containsKey(target - nums[i])) {
                answer = new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }

        return answer;
    }
}

결과

시간	메모리
4 ms	43.3 MB

---

1차 시도

1. 풀이 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int N = nums.length;
        
        int[] answer = {};

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) {
                    continue;
                }
                int sum = nums[i] + nums[j];

                if (sum == target) {
                    answer = new int[]{i, j};
                }
            }
        }

        return answer;
    }
}

2. 문제점

• 시간 복잡도가 O(N^2)으로 시간이 오래 걸리는 문제점이 있다.

3. 결과

 

2차 시도

1. 풀이 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int N = nums.length;
        
        int[] answer = {};
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            if (map.containsKey(target - nums[i])) {
                answer = new int[]{i, map.get(target - nums[i])};
            }
            map.put(nums[i], i);
        }

        return answer;
    }
}

2. 1차 시도 개선점

• N * N 만큼 반복하는 연산 수를 N으로 감소시켰다.
• 값을 Key로 인덱스를 Value로 하는 HashMap을 선언해서 값들을 저장하고, target에서 현재 자리의 수를 뺀 값이 HashMap에 존재하면 현재 수와 HashMap안에 있는 수의 합이 target이 되는 경우이므로 인덱스를 반환한다.
• HashMap을 사용하면 N번의 연산 수로 문제를 해결할 수 있다.

3. 결과