[Algorithm] 투포인터 - 두 수의 합(Python)

n개의 요소를 가진 배열이 있다. 
[2, 5, 3, 4, 12, 7, 9, 11]
이 배열에서 두 수의 합이 10이 되는 수들의 인덱스를 출력하라.

풀이1-이중반복문

numberArray = [2, 5, 3, 4, 12, 7, 9, 11]
n = len(numberArray)
target = 10

for i in range(n):
    for j in range(n):
        if numberArray[i] + numberArray[j] == target:
            print(i,j)

시간복잡도 = O(n²)

풀이2-투포인터

numberArray = [2, 5, 3, 4, 12, 7, 9, 11]
n = len(numberArray)
target = 10

startPointer, endPointer = 0, n-1
numberArray.sort()

while startPointer != endPointer:
    if numberArray[startPointer] + numberArray[endPointer] == target:
        print(startPointer, endPointer)
    elif numberArray[startPointer] + numberArray[endPointer] > target:
        endPointer-=1
    else:
        startPointer+=1

시간복잡도 = O(nlogn)

 

파이썬의 정렬함수는 O(nlogn)의 시간복잡도를 가지고 투포인터에서 O(n)의 시간복잡도를 가지므로
전체 시간복잡도는 O(nlogn)이 된다.