[LeetCode] 1. Two Sum #Easy #Java

문제
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.

예제 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
// Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

예제 2

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

예제 3

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

 제약조건

✅ 2 <= nums.length <= 104

✅ -109 <= nums[i] <= 109

✅ -109 <= target <= 109

✅ Only one valid answer exists.

문제풀이 1

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

굉장히 많은 사람들이 10ms보다 빠른 속도로 문제를 해결했다.
이는 곧 본인의 풀이는 접근이 잘못되었다는 것을 의미한다. 더 개선해 보자.

 
문제풀이 2

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 1. 변수 선언 및 초기화
        Map<Integer, Integer> idxMap = new HashMap<>();
        int[] result = new int[2];

        // 2. 순회하며 두 값의 합이 target인 경우 탐색
        int idx = 0;
        for (int num : nums) {
            // 해당 원소 키 값이 존재한다면 반환
            if (idxMap.containsKey(num)) result = new int[] { idxMap.get(num), idx };
            
            // target - nums[idx]와 idx의 키-값쌍 저장
            int theOtherNum = target - nums[idx];
            idxMap.put(theOtherNum, idx);

            // 인덱스 증가
            idx++;
        }

        // 3. 반환
        return result;
    }
}

• 이중 for문이 가장 문제라고 생각해서 단일 for문과 함께 해시맵을 사용하였다.
• 배열을 순회하며 현재 값이 이전 값들의 target - nums[idx]에 해당하는지 확인하는 것이다. 

 

마치며

이 문제 난이도가 easy인데 적당히 이중 for문으로 풀면 쉽긴 하지만 개선하는 방법을 찾는 건 조금 생각이 필요한 것 같다.
이것보다 빠르게 해결하신 분들은 어떻게 하신 건지 궁금하다. 😮

 

이미지 출처

[김은우의 에듀테크 트렌드 따라잡기] 코딩 교육 사이트 LeetCode가 보여주는 코딩교육의 핵심