문제 이해
•
배열에서 2개의 숫자끼리 더해서 target이 되는 조합이 딱 1개가 있다.
•
이 문제는 순서가 상관이 없는 조합을 찾는 문제
접근 방법
•
1차로 가장 바로 생각난 방법은 이중 반복문 돌려서 target이 되는 2개의 인덱스 조합을 찾자.
•
시간 복잡도도 2 <= nums.length <= 10^4 로 총 대략적으로 O(n^2)해서 10^8 정도로 시간초과가 나지 않을까? 했는데 일단은 이중 반복문으로 한번 문제 풀이 시도.
◦
시간 초과 발생X
•
그리고 순서가 상관이 없었기 때문에 j는 i+1로 설정하여 (0,1) (1,0) 이렇게 중복 검사하는 케이스 제외
통과 코드
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i=0; i<nums.length; 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};
}
}
Java
복사
1차 풀이
최적화 코드
import java.util.*;
class Solution {
public int[] twoSum(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[]{i, map.get(target-nums[i])};
}else {
map.put(nums[i], i);
}
}
return new int[]{0, 0};
}
}
Java
복사
느낀점
•
한 문제에 대해서 여러가지 풀이법 존재..
멘토님 피드백
•
