[LeetCode 1] Two Sum (Java)

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

---

풀이

이 문제는 정수 배열 nums와 정수 target이 주어졌을 때, nums의 두 원소들의 합이 target이 되는 원소들의 인덱스들을 리턴하는 문제이다.

1. 브루트 포스

가장 먼저, 가능한 모든 경우가 target이 되는지 확인하는 것이 가능할 것이다.

문제의 제약 조건이 2 <= nums.length <= 10000이므로, 시간복잡도가 $O(N^2)$ 인 브루트포스는 시간초과가 발생하지 않는다.

이를 코드로 옮기면 다음과 같다.

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

2. 해시

다음으로, 현재인 i번째 이전까지의 원소들이 몇번 인덱스인지 기록해 두는 것이다.

만약 기록이 되어 있다면, 해당 원소는 i번째 이전에 나온적이 있는 원소이다.

그러므로, target - nums[i]가 나타난 적이 있는 원소라면, 해당 원소와 nums[i]를 더해 target을 만들 수 있으므로, 이 둘의 인덱스를 리턴하여 문제를 해결할 수 있을 것이다.

이를 코드로 옮기면 다음과 같다.

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