투포인터 알고리즘 구현해보기

투포인터 알고리즘 : 배열의 인덱스를 나타내는 두개의 포인터를 설정하고, 이를 옮겨가면서 내가 원하는 값을 찾는 알고리즘

 

 

ex) [1, 5, 4, 6, 4] 에서 연속된 배열의 합이 10인 배열의 인덱스를 모두 찾아라.

start : 0, end : 0, array : [1] , sum : 1 / sum이 10보다 작음. end 증가

start : 0, end : 1, array : [1, 5] , sum : 6 / sum이 10보다 작음. end 증가

start : 0, end : 2, array : [1, 5, 4] , sum : 10 / sum이 10 찾음. start 증가

start : 1, end : 2, array : [5, 4] , sum : 9 / sum이 10보다 작음. end 증가

start : 1, end : 3, array : [5, 4, 6] , sum : 15 / sum이 10보다 큼. start 증가

start : 2, end : 3, array : [4, 6] , sum : 10 / sum이 10 찾음. start 증가

start : 3, end : 3, array : [6] , sum : 6 / sum이 10보다 작음. end 증가

start : 3, end : 4, array : [6, 4] , sum : 10 / sum이 10찾음. start 증가

start : 4, end : 4, array : [4] , sum : 4 / 종료

 

def 투포인터(mylist, mysum):

    start = 0 # start포인터
    end = 0 # end포인터
    tempsum = 0 # 배열의 합

    result = [] # 결과 인덱스 넣을 배열

    for start in range(len(mylist)): # start포인터의 반복 범위 설정
        while tempsum < mysum and end < len(mylist): # 합이 작고 end포인터가 배열 범위를 벗어나지 않았으면 반복
            tempsum += mylist[end] # 배열의 합에 넣기
            end += 1 # 합이 작으니까 end포인터 증가
        if tempsum == mysum: # 합과 같으면
            result.append([start, end - 1]) # 결과에 인덱스 추가
        tempsum -= mylist[start] # 다음 start포인터 증가를 위해 배열의 합에서 빼기

    return result

투포인터([1, 5, 4, 6, 4], 10) # [[0, 2], [2, 3], [3, 4]]

 

슬라이딩 윈도우 알고리즘 : 인덱스의 간격이 일정한 투포인터 알고리즘