문제
비감소 순서로 이미 정렬된 정수 배열 numbers가 주어집니다. 이 배열에서 두 수를 찾아야 하는데, 이 두 수의 합이 특정한 목표 숫자(target)가 되어야 합니다. 이 두 수를 numbers[index1]와 numbers[index2]라고 할 때, 1 <= index1 < index2 < numbers.length의 조건을 만족해야 합니다.
두 숫자의 인덱스, index1과 index2,를 1씩 더하여 길이가 2인 정수 배열 [index1, index2]로 반환하세요.
테스트 케이스는 정확히 하나의 해결책이 존재하도록 생성됩니다. 같은 요소를 두 번 사용할 수 없습니다.
해결책은 상수 공간만을 사용해야 합니다.
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].
풀이
class Solution {
public int[] twoSum(int[] numbers, int target) {
// 1. 해시맵 생성
Map<Integer, Integer> result = new HashMap<>();
// 2. numbers 배열을 순회하면서
for (int i = 0; i<numbers.length; i++) {
// 3. 해시맵에 targer - number[i] 이 존재하는지 확인
if (result.containsKey(target - numbers[i])) {
// 4. 존재하면 [i+1, value+1] 반환
return new int[]{result.get(target - numbers[i]) + 1, i+1};
}
// 5. 존재하지 않으면 해시맵에 저장
result.put(numbers[i], i);
}
return new int[]{0,0};
}
}- Hash 를 이용하여 방문목록에 target - num 이 존재하는지 확인하는 방법
- O(N) 의 시간복잡도
- O(N) 의 공간복잡도
다른풀이
상수 공간만 사용해야 한다는 조건에 맞지 않음.
배열이 이미 정렬되어 있으니, 공간복잡도를 상수로 만들 수 있음.
class Solution {
public int[] twoSum(int[] numbers, int target) {
// 1. two pointer 생성
int left = 0;
int right = numbers.length-1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
// 4. 합이 target 과 일치하면 해당 인덱스 배열 반환
return new int[] {left+1, right+1};
} else if (sum < target) {
// 3. 두 포인터 요소 합이 target 보다 작으면 left 를 이동해 합을 증가
left++;
} else {
// 2. 두 포인터 요소 합이 target 보다 크면 right 를 이동해 합을 감소
right--;
}
}
return new int[]{0,0};
}
}