문제 이해
- 배열에서 Target과 일치하는 두 수의 합을 구하라
해결 전략
(1) O(n2)으로 문제를 풀이하면, 2중 for문을 순회하면서 목표하는 target을 구할 수 있습니다.
(2) O(n)으로 문제를 풀이하면, HashMap을 사용해서 목표하는 target을 구할 수 있습니다.
구현
(1) O(n2)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] answer = new int[2];
for(int i=0; i<nums.length; i++){
for(int j=i+1; j<nums.length; j++){
if(nums[i] + nums[j] == target){
answer[0] = i;
answer[1] = j;
}
}
}
return answer;
}
}
(2) O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] answer = new int[2];
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<nums.length; i++){
if(map.containsKey(target-nums[i])){
answer[1] = i;
answer[0] = map.get(target-nums[i]);
return answer;
}
map.put(nums[i], i);
}
return answer;
}
}
피드백
- HashMap을 사용해 O(n)으로 문제를 풀이하는 법을 아는 것이 중요합니다.
- HashMap의 내부 구조에 대해서도 잘 알아야 합니다.
'PS' 카테고리의 다른 글
Leetcode 2. Add Two Numbers (0) | 2022.04.30 |
---|---|
Leetcode 21. Merge Two Sorted Lists (2) | 2022.04.26 |
Leetcode 234. Palindrome Linked List (1) | 2022.04.26 |
Leetcode 203. Remove Linked List Elements (1) | 2022.04.26 |
Leetcode 876. Middle of the Linked List (0) | 2022.04.25 |