[leetcode] twosum (java)

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

풀이법 3가지

1. 중첩 for문을 이용해서 배열의 요소를 차례차례 읽어 간다.  => 시간 복잡도 O(N^2)으로 인해 비효율적

 

2. hashtable을 이용 - 값을 꺼내는데 O(N)

   2-i) 아래 예제에서 int[] nums = new int[]{1,2,3,4}; 의 값을 전부 미리 넣어 놓고 값을 찾는다.

   hashmap에는  key는 찾고자 하는값, value는 index

   2-ii) 값을 비교하면서 찾고자 하는 데이터가 있으면 return 없으면, hashmap에 넣는다.

public class TwoSum {
	
	public static void main(String[] args) {
		TwoSum twosum = new TwoSum();
		int[] nums = new int[]{1,2,3,4};
		int target = 6;
		
		System.out.println(Arrays.toString(twosum.twoSum1(nums, target)));
		System.out.println(Arrays.toString(twosum.twoSum2(nums, target)));
	}
	
	// i
	public int[] twoSum1(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for( int i=0; i< nums.length; i++) {
			map.put(nums[i], i);
		}
		for(int i1 = 0; i1 < nums.length; i1++) {
			Integer i2 = map.get(target - nums[i1]);
			if (i2 != null && i1 != i2) return new int[]{i1, i2};
		}		
		throw new IllegalArgumentException("no two sum solution");		
	}
		
	// ii
	public int[] twoSum2(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for( int i=0; i< nums.length; i++) {
			if(map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i };
			map.put(nums[i], i);
		}		
		throw new IllegalArgumentException("no two sum solution");		
	}

}

Reference

https://www.youtube.com/watch?v=FHphOv2mmIA