[LeetCode/Top Interview 150] [Hash Table] 1. Two Sum

문제 링크: https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

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

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

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

전략:

단 하나의 정답이 존재한다. O(n^2)보다 낮은 시간 복잡도를 가진 알고리즘이 존재함.

두 수의 합이 타겟이 되는 수 찾아서 인덱스 리턴하기(요소 중복 사용 불가)
음수값이 가능하므로 보다 큰 수여도 정답이 가능함.
처음에 전체 배열을 for문으로 돌면서 값과 인덱스를 HashMap에 저장(값이 중복되는 경우는 아래for문에서 체크하도록 하면 되므로 Integer로 value를 저장)하고, 아래에서 다시 for문을 돌면서 타겟에서 현재 요소를 뺀 값을 키로 가지는 요소가 HashMap에 존재하는지 체크(키가 현재 요소의 값과 같은 경우(즉, 동일한 값을 가진 두 수를 더해서 타겟이 되는 경우), 현재 인덱스와 HashMap에 저장된 인덱스가 다른 경우에만 정답으로 리턴)

코드 구현:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i=0;i<nums.length;i++) {
            map.put(nums[i],i);
        }
        for (int i=0;i<nums.length;i++) {
            int num2 = target-nums[i]; // 현재 숫자 nums[i]와 합하여 target이 되는 숫자
            int num2_idx = map.getOrDefault(num2, -1);
            // num2의 인덱스값 (존재한다면 해당 인덱스, 존재하지 않는다면 -1 리턴)
            if (num2_idx == -1) continue; // num2 없으면 continue;            
            if (nums[i]!=num2 || i!=num2_idx) { // 요소를 중복사용하지 않았다면 정답
                return new int[] {i, num2_idx};
                // 순서는 상관 없으므로 정답이 나오는 순간 즉시 리턴
            }
        }
        // 정답 조합이 존재하지 않는 경우. (문제에서는 정답이 반드시 존재한다.)
        return new int[] {-1, -1};
    }
}

실행결과:
Time: 4 ms (66.24%), Space: 44 MB (11.83%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0001-two-sum/0001-two-sum.java

개선 방안:

for 문 2개이던 것을 1개로 합쳐서 입력과 동시에 체크하기.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i=0;i<nums.length;i++) {
            int num2 = target-nums[i]; // 현재 숫자 nums[i]와 합하여 target이 되는 숫자
            int num2_idx = map.getOrDefault(num2, -1);
            // num2의 인덱스값 (존재한다면 해당 인덱스, 존재하지 않는다면 -1 리턴)
            map.put(nums[i],i);
            if (num2_idx == -1) continue; // num2 없으면 continue;
            if (nums[i]!=num2 || i!=num2_idx) { // 요소를 중복사용하지 않았다면 정답
                return new int[] {i, num2_idx};
                // 순서는 상관 없으므로 정답이 나오는 순간 즉시 리턴
            }            
        }
        // 정답 조합이 존재하지 않는 경우. (문제에서는 정답이 반드시 존재한다.)
        return new int[] {-1, -1};
    }
}
Time: 2 ms (82.8%), Space: 43.4 MB (94.96%) - LeetHub

Solutions 탭의 타인 코드:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < numbers.length; map.put(numbers[i], i++)) 
            if (map.containsKey(target - numbers[i])) 
                return new int[]{map.get(target - numbers[i]),i};
        return new int[]{0,0};
    }
}
Time: 1 ms (99.41%), Space: 43.5 MB (89.09%) - LeetHub

회고:

containsKey를 사용할 생각은 못 했었는데 확실히 코드도 짧아지고, 더 나은 코드인 것 같다.