https://leetcode.com/problems/two-sum/
정수 배열과 target이 주어졌을 때, 배열에서 선택한 두 값의 합이 target값과 같아지도록 하는 값의 인덱스를 구한다.
문제를 처음 보았을 때 직관적으로 이중 for문을 활용하여 풀어야겠다고 생각했다.
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length - 1; ++i){
for(int j =i+1;j<nums.length; ++j){
if(nums[i]+ nums[j] == target){
return new int[] {i,j};
}
}
}
return new int[] {0, 0};
}
}
그 결과 시간 복잡도가 상위 77%가 나왔다.
자료구조를 잘 활용하면 시간복잡도 개선할 수 있다.
정수 값을 key로 갖고, 배열의 인덱스를 value로 가지는 map을 이용하여 문제를 해결하였다.
import java.util.HashMap;
import java.util.Map;
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
if (map.containsKey(target - nums[i])) {
return new int[] { i, map.get(target - nums[i]) };
}
map.put(nums[i], i); // put number and index
}
return new int[] {};
}
}