int 배열이 주어지고 target이 주어지면 2개의 조합으로 target이 되는 조합을 반환하는 문제입니다.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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]
문제접근
투포인터를 사용해서 O(n)으로 해결할 수 있다고 판단하여 투포인터를 사용했습니다.
하지만 투포인터로는 정답을 받을수 없었습니다.
왜냐하면 배열의 요소들이 정렬되어있지 않기때문입니다.
만약 정렬을 한다면 index가 바뀌어값을 찾기 어렵습니다.
투포인터 - 실패
더보기
public int[] twoSum(int[] nums, int target) {
Arrays.sort(nums);
int l = 0;
int r = nums.length - 1;
while (l <= r) {
int cur = nums[l] + nums[r];
if (cur == target) {
return new int[]{l,r};
} else if (cur > target) {
r--;
} else {
l--;
}
}
return new int[]{};
}
다른방법이 떠오르지않아 브루트포스를 이용해서 문제를 풀었습니다.
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[]{};
}
시간복잡도
for문을 2번사용하고 있습니다.
O(n2)의 시간복잡도를 갖고있습니다.
다른사람의 풀이
해시테이블을 사용한 풀이입니다.
해시테이블에 nums[i] : 키, val : 값 저장합니다.
target - nums[i]가 해시테이블에 있다면 정답을 찾은것입니다.
주의할점은 자기 자신을 더하면 안됩다는 것입니다.
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i],i);
}
for (int i = 0; i < nums.length; i++) {
int rest = target - nums[i];
if (map.containsKey(rest) && map.get(rest) != i) {
return new int[]{i, map.get(rest)};
}
}
return new int[]{};
}
시간복잡도
Map의 조회, 삽입의 시간복잡도는 O(1)입니다.
따라서 nums배열을 1번 loop하는 로직이 최대이니
O(n)의 시간복잡도가 필요합니다.
느낀점
Map은 시간을 단축하기 정말 좋은 자료구조입니다.
메모리를 소비하는 단점이 있지만, 잘 활용한다면 효율적인 코드를 작성할 수 있을것 같습니다.
참고
'LeetCode' 카테고리의 다른 글
[LeetCode] 383. Ransom Note (0) | 2023.08.31 |
---|---|
[LeetCode] 219. Contains Duplicate II (0) | 2023.08.31 |
[LeetCode] 155. Min Stack (0) | 2023.08.30 |
[LeetCode] 74. Search a 2D Matrix (0) | 2023.08.29 |
[LeetCode] 21. Merge Two Sorted Lists (0) | 2023.08.29 |