[알고리즘 종류] 투 포인터(Two Pointer)

- 투포인터

• 리스트에 순차적으로 접근해야 할 때 시작점과 끝점 위치를 기록하면서 접근
• N개의 원소를 가진 배열에서 특정 조건을 만족하는 연속적인 원소들의 집합을 구하는 알고리즘
• 시간 복잡도: O(N)

📄 활용예제

- 특정 합을 가지는 부분 연속 수열 찾기

- 정렬되어 있는 두 리스트의 합집합

 

def two_pointer(lst, target):
    left, right = 0,0
    cnt = 0
    total = 0

    while left < len(lst):
        if total == target:
            cnt += 1
            total -= lst[left]
            left += 1
        elif total > target or right >= len(lst): # 이 부분율 유심히 보길 바란다.
            total -= lst[left]
            left += 1
        elif total < target:
            total += lst[right]
            right += 1

    return cnt

lst = [7,5,2,4,3,2]
print(two_pointer(lst, 7)