HashMap, Two Sum

Problem

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.

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

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

문제 해석

My Approach

접근 방법에 따른 trade-off (시간 복잡도 <-> 공간 복잡도)

접근 1. Brute-force 모든 조합을 시도, 이중 loop n * (n + 1) / 2

• Time: O(n^2)
• Space: O(1)

접근 2. 해쉬 맵(HashMap) 사용, loop를 한번 돌면서 이미 봤던 값은 해쉬 맵에 저장

• 타겟값에서 현재 인덱스에 해당하는 요소의 값을 뺀 값이 이미 해쉬 맵에 가지고 있는지 확인
• Time: O(n)
• Space: O(n)

Brute-force 모든 조합을 시도

class Solution {
	public int[] twoSum(int[] nums, int target) {
		for(int i=0; i<nums.length; i++){
			for(int j=0; j<nums.length; j++){
				if(nums[i]+nums[j] == target){
					int[] ret = new int[2];
					ret[0] = i;
					ret[1] = j;
					return ret;
				}
			}
		}
		throw new IllegalArgumentException("No two sum solution");
	}
}

HashMap 사용

HashMap을 미리 채우고 loop를 다시 돌면서 타겟 값을 찾는 방법

class Solution {
	public int[] twoSum(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<>();
		for(int i=0; i < nums.length; i++){
			map.put(nums[i], i);
		}

		for(int j=0; j < nums.length; j++){
			Integer i2 =  map.get(target - nums[i]);
			if(i2 != null && j != i2){
				return new int[]{j, i2};
			}
		}
		throw new IllegalArgumentException("No two sum solution");
	}
}

loop를 돌면서 HashMap도 채우고 값도 찾는 방법

class Solution {
	public int[] twoSum(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < nums.length; i++){
			int cur = nums[i];
			if(map.containsKey(target-cur)){
				int[] ret = new int[2];
				ret[0] = map.get(target-cur);
				ret[1] = i;
				return ret;
			} else {
				map.put(cur,i);
			}
		}
		return null;
		//throw new IllegalArgumentException("No two sum solution");
	}
}