int 배열 numbers와 tartget 숫자가 주어지면 numbers안에 요소 2개를 더해 target이 되는 인덱스들을 반환하는 문제입니다.
문제접근
문제는 단순하게 접근하였습니다.
배열안에서 두개의 값을 비교해야하기때문에 투포인터를 사용해봐야겠다고 생각했습니다.
start와 end를 정해두고 num[start] + num[end]가
target보다 크다면 end--
target보다 작다면 start++
target과 같다면 start+1, end+1을 반환하였습니다.
public int[] twoSum(int[] numbers, int target) {
int start = 0;
int end = numbers.length-1;
while (start <= end){
int cur = numbers[start] + numbers[end];
System.out.println(cur + " " + start + " " + end);
if (cur > target) {
end--;
} else if (cur < target) {
start++;
} else {
return new int[]{start+1, end+1};
}
}
return new int[]{};
}
시간복잡도
최악의 경우 end 또는 start가 끝까지 가야하므로 O(n)의 시간복잡도를 갖고있습니다.
다른사람의 풀이
같은 투포인터를 사용했지만, while문의 조건을 더 잘 활용하였습니다.
public int[] twoSum(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (nums[l] + nums[r] != target) {
if (nums[l] + nums[r] < target) l++;
else r--;
}
return new int[] {l+1, r+1};
}
느낀점
이번에는 배열의 두요소를 컨트롤해야한다는 점을 알고 투포인터를 잘 활용한것 같습니다.
하지만 while문을 잘 활용하기위해 while문의 조건을 좀 더 잘 다뤄야겠다고 생각했습니다.
그이유는 조건을 잘 설정하면 코드의 가독성이 더 높아지기 때문입니다.
참고
'LeetCode' 카테고리의 다른 글
[LeetCode] 3. Longest Substring Without Repeating Characters (1) | 2023.08.28 |
---|---|
[LeetCode] 209. Minimum Size Subarray Sum (0) | 2023.08.28 |
[LeetCode] 125. Valid Palindrome (1) | 2023.08.27 |
[LeetCode] 55. Jump Game (0) | 2023.08.25 |
[LeetCode] 122. Best Time to Buy and Sell Stock II (0) | 2023.08.25 |