[Hash Table] Two Sum

투섬

Two Sum - LeetCode

정수 배열 nums 과 정수가 주어지면 두 숫자의 합이 가 되는 인덱스를target 반환합니다 .target

각 입력에는 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다 .

어떤 순서로든 답변을 반환할 수 있습니다.

 

예시 1:

입력: nums = [2,7,11,15], target = 9
 출력: [0,1]
 설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.

예 2:

입력: 숫자 = [3,2,4], 대상 = 6
 출력: [1,2]

예시 3:

입력: 숫자 = [3,3], 대상 = 6
 출력: [0,1]

 

제약:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 유효한 답은 하나만 존재합니다.

---

문제 풀이 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];

        for(int i = 0 ; i < nums.length ; i ++){
            for(int j = i+1; j < nums.length ; j ++){

                if(target == nums[i] + nums[j]){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
                
            }
        }
        return result;
    }
}

순회를 두번하여 nums[i] + nums[j] = target 이 되는 i , j 를 반환하여 풀었습니다.

이런 방식으로 문제를 풀면 O(n^2)의 시간복잡도가 나옵니다. 이러한 방식은 추천하지 않는 방식입니다.

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }

        return new int[]{};
    }
    
}

그리하여 다른 솔루션을 찾아 봤습니다. 

여기서는 보수와 HashMap의 containsKey를 사용하여 풀었다.

현재 idx를 value로 보수값을 key로 설정하였고

순회하며 nums[i]의 보수가 있는 지 확인한다 

보수가 있을 경우 현재수를 보수로 갖던 수의 index와 현재 index를 반환하여 풀이하였다.

이러한 솔루션은 O(n)의 시간복잡도로 횔씬 빨라졌다.