[JAVA][Array] TwoSum

1. 문제

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15],
target = 9,
Because nums [0] + nums [1] = 2 + 7 = 9,
return [0, 1].

 

2. 문제해설

target의 숫자를 nums 배열에 있는 숫자 2개의 합으로 만들 수 있는데 어느 인덱스에 있는 숫자를 활용해야 하는지 구하라(단, 같은 숫자를 사용할 수는 없다. 경우의 수는 1가지 이다.)

 

3. 코드 포맷

public class TwoSum {

	public static void main(String[] args) {
		int[] nums = {5,8,5,2};
        int target =10;
        TwoSum a = new TwoSum();
        int[]  result = a.solve(nums, target);
        for(int i : result)
        	System.out.println(i);
	}
}

 

4. 접근 방법

nums의 배열에 있는 숫자를 1개씩 더해보면서 답을 구한다.

5. 코드

public class TwoSum {

	public static void main(String[] args) {
		int[] nums = {4,8,6,2};
        int target =10;
        TwoSum a = new TwoSum();
        int[]  result = a.solve(nums, target);
        for(int i : result)
        	System.out.println(i);
	}

	private int[] solve(int[] nums, int target) {
		//결과
		int[] result = new int[2];
		//검색을 용이하도록 map 사용, key: target에서 뺀 나머지 / value: 인덱스값
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		//2차원 배열 사용
		for(int i=0;i<nums.length;i++) {
			if(map.containsKey(nums[i])&& target-nums[i]!=nums[i]) {
				result[0]=map.get(nums[i]);
				result[1]=i;
			}
			else
				map.put(target-nums[i], i);
		}
		return result;
	}
}