Two-Sum-사전 정렬 최적화 알고리즘 설계
🧩 오름차순 또는 내림차순으로 사전 정렬 된 입력을 수신하여 2- 합 솔루션의 런타임을 최적화 할 수 있습니까?
🚀 오리지널 Two-Sum
동일한 항목을 두 번 선택할 수 없도록 개별 용량이 총 용량과 완벽하게 동일한 두 항목이 있는지 확인합니다.
- 입력 : 총 용량을 나타내는 Int와 항목의 개별 용량을 나타내는 Int의 배열.
- 출력 : 두 항목이 총 용량과 같을 수 있는지 여부를 나타내는 부울입니다.
- 시간 복잡성 : 선형 성장, $O(n)$
- 공간 복잡성 : 선형 성장, $O(n)$
견본
입력: [4, 5, 2, 6]
- 총 용량 :
10
- 배고 있다:
true
입력: [4, 5, 2, 5]
- 총 용량 :
10
- 배고 있다:
true
입력: [4, 5, 2, 7]
- 총 용량 :
10
- 배고 있다:
false
의사 코드
searchSet
이미 검사 한 항목을 저장할 세트 를 만듭니다 .항목 용량의 입력 배열을 반복합니다.
2a.
targetCapacity
현재 항목 찾기 :totalCapacity - itemCapacity
2b. 를
searchSet
포함하는targetCapacity
경우를 반환true
합니다.2c. 그렇지는 추가
itemCapacity
받는 사람searchSet
.false
일치하는 항목을 찾지 않고 전체 입력이 반복되는 경우 반환 합니다.
🏗️ 사전 정렬
- 새 변수 저장
lastTargetCapacity
- 현재
itemCapacity
<lastTargetCapacity
이면 가능한 두 합계 및 반환이 없습니다false
.
즉
입력: [6,2,1,0]
- 총 용량 :
9
반복
targetCapacity = 9 - 6
,lastTargetCapacity
= 3- 때문에 거짓 반환
itemCapacity
의2
<lastTargetCapacity
의3
.
답변
Two Sum 솔루션은 입력 배열이 오름차순 또는 내림차순으로 미리 정렬되어 있으므로 런타임 성능을 위해 최적화 할 수 있습니다.
이진 검색을 사용하여 targetCapacity
위 를 찾으면 로그로 실행되며,$O(logn)$, 평균 런타임. 이것은 선형으로 실행되는 위의 의사 코드보다 빠릅니다.$O(n)$, 반복 및 해싱을 사용하는 런타임.
입력에 정렬이 제공되지 않으면 다음보다 빠르게 정렬 및 검색 할 수 없습니다. $O(n)$. 할 수있는 최선은$O(nlogn)$ Quicksort 및 Binary Search와 같은 전략을 사용합니다.
참조 : Stanford-Two Sum 설명
예, 다음에서 2 합 문제를 해결할 수 있습니다. $O(n)$시간, 숫자가 정렬 된 순서로 표시되는 경우. 방법은 다른 답변 을 참조하십시오 . 선형 스캔이 포함됩니다. 이미 소요되므로 점근 적으로 최적입니다.$O(n)$ 입력을 읽는 데에도 시간이 걸리고 문제를 해결하려면 전체 입력을 읽어야 할 수 있으므로 점근 적 개선이 더 이상 없습니다.