[HashTable] 1. Two Sum

문제

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 <= 104-109 <= nums[i] <= 109-109 <= target <= 109Only one valid answer exists.

 

문제 접근

 i 와 j 의 합을 탐색하며 두개의 수를 합한 값을 target과 비교한다.

 

문제 풀이

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

        return result;
    }
}

 

다른풀이 및 회고

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

 

HashTable을 모든 값과 인덱스를 저장하고 target과 현재 탐색 값의 차를 포함여부를 확인하면 손쉽게 시간 복잡도를 O(n) 으로 해결 할 수 있다.