[LeetCode/Top Interview 150] [Two Pointers] 167. Two Sum II - Input Array Is Sorted
LeetCode Top Interview 150
문제 링크: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)
난이도: medium
문제:
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].Constraints:
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
-1000 <= target <= 1000
The tests are generated such that there is exactly one solution.
전략:
이미 비내림차순으로 정렬된 인덱스가 1부터 시작하는 배열이 주어지는데, 서로를 더하면 타겟 넘버가 나오는 두 수를 찾아 그 인덱스를 오름차순 배열으로 반환해야 한다. (같은 원소를 2번 사용할 수 없으며, 테스트케이스는 오직 1개의 답만 가지도록 되어있다.)
공간복잡도는 상수(O(1))의 복잡도를 가져야 한다.
-> 시간 복잡도는 별 얘기 없었으니 일단 이중 for문으로 통과는 되는지 보기!
코드 구현:
class Solution {
public int[] twoSum(int[] numbers, int target) {
for (int i=0;i<numbers.length;i++) {
for (int j=i+1;j<numbers.length;j++) {
if (target == numbers[i] + numbers[j]) {
return new int[] {i+1,j+1};
}
}
}
return new int[] {-1,-1};
}
}실행결과:
Time: 405 ms (5.04%), Space: 45.2 MB (91.92%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0167-two-sum-ii-input-array-is-sorted/0167-two-sum-ii-input-array-is-sorted.java
개선 방안:
통과를 시켜주기는 하는데 역시 처참한 성능이다.
이제 진짜 투포인터를 적용해서 풀어봐야겠다.두 수를 더해서 target을 만드는 경우, 두 수 모두 target보다 작은 수인 경우와 한 수는 target 보다 크고, 다른 수는 음수의 값을 가지는 경우, 그리고 target과 같은 수 + 0인 3가지의 경우가 존재한다.
우선 배열의 양 끝단 가장 작은 수와 가장 큰 수를 합하고, 이 수가 타겟과 같고, 두 수가 같은 인덱스를 가지고 있지 않다면 즉시 리턴, 타겟보다 크다면 큰 수를 한 단계 작은 수로 바꾸고, 타겟보다 작다면 작은 수를 한 단계 큰 수로 바꾼다. 이를 타겟이 나올 때까지 반복한다.그런데 굳이 정답이 반드시 하나 존재한다는 조건을 걸고 문제에 적은 이유는 이걸 활용해서 더 빨리 풀 수 있는 방법이 존재하는 것일까? 아니면 그냥 답이 나온 시점에서 다른 답을 더 찾을 필요 없이 바로 리턴해도 된다는 의미일까?
class Solution {
public int[] twoSum(int[] numbers, int target) {
int min_idx = 0;
int max_idx = numbers.length-1;
while (min_idx<max_idx) {
int min = numbers[min_idx];
int max = numbers[max_idx];
if (min + max == target) { // 이 부분에서 두 요소의 idx값이 동일하지 않은지도 체크하고자 했었지만 성능을 위해서 일단 뺌
return new int[] {min_idx+1, max_idx+1};
} else if (min + max < target) {
min_idx++;
} else if (min + max > target) {
max_idx--;
}
}
// 배열의 요소들을 다 체크해도 답이 없는 경우
// 사실 이 문제에서는 테스트 케이스에서 답의 존재를 보장했으니 그냥 여기서 return new int[] {min_idx+1, max_idx+1};로 리턴했어도 문제는 없었겠지만, 혹시 입력 배열에 정답이 없는 경우를 생각해서 남겨뒀다.
return new int[] {-1,-1};
}
}
Time: 1 ms (99.41%), Space: 45.1 MB (95.73%) - LeetHub투포인터를 사용해도 이 정도 퍼센티지라면 보다 나은 방법이 있는 건가 생각했었는데 여러 번 제출해본 결과 같은 코드도 1ms와 2ms에서 큰 차이가 나는 걸 보니 제출 시점의 서버 상태에 영향을 받을 만큼 작은 복잡도를 가진 문제라서인가보다.
원래는 (min_idx != max_idx) 조건도 리턴하기 전에 체크해 줬었는데 비 내림차순이고, 문제에서 정답이 존재한다는 것을 보증해줬으므로 성능을 위해서 제거했다.
Discuss 탭의 타인 코드:
class Solution {
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};
}
}
// 내 코드와 유사한 방식회고:
처음에 냅다 이중 for문으로 해도 통과를 시켜줄까 궁금해서 제출해 봤는데 진짜 통과가 되어서 조금 놀랐다. 투포인터로 코드를 수정한 다음에는 순위 욕심으로 원하는 퍼센티지가 나올 때까지 돌려서 결국 원하던 99%를 얻어냈다. 문제 자체는 크게 어렵지 않았던 것 같다.
