https://leetcode.com/problems/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.
해석: 정수의 배열 num과 정수 target을 입력받아, 합했을시 target의 수가 나오게되는 num배열의 두 인덱스값을 배열로 리턴하는 함수를 작성하시오
각 인풋에는 항상 답이있다고 가정하며, 배열안의 요소를 중복해서 더할수는 없다.
정답이 되는 인덱스값의 배열상 배치순서는 상관없다.
예시)
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]제약사항
- 2 <= nums.length <= 10^3
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Only one valid answer exists.
풀이
import java.util.*;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int i = 0;
while (i < nums.length)
{
if (map.containsKey(nums[i]))
return new int[] {map.get(nums[i]), i};
map.put(target - nums[i], i);
i++;
}
return new int[] {};
}
}타겟이 요구하는 숫자를 구성하는 배열의 인덱스값을 어떻게하면 찾아낼수있을까?
완전탐색으로 더해보고 비교하는게 가장 생각하기 쉬운것같다. 그러나 가장 느릴듯하다.
더하기를 다르게 생각해보면 a + b = target => b = target - a 인데, 이걸 이용해보는건 어떨까.
이렇게 생각하면 target에서 지금 보는 배열의 요소를 빼~고 "남은 값"이 "또하나의 답"이된다. 바로 이 남은 값을 키값으로 두는것이 포인트인데, 이렇게 해쉬맵을 구성하면 다음 비교때 map.containsKey(nums[i])로 지금까지 구성한 해쉬맵의 키값을 충족하는 답인지를 바로 판단할수있게된다. 해쉬맵에서 탐색은 O(1)이기 때문에 매우 빠르게 답을 찾아낼수있을것이다.
그렇게 해서 리턴은 찾아낸 키값의 밸류값과 지금본 인덱스값으로 만들어주면 끝!
