파이썬(python) 투 포인터

투 포인터

리스트에 순차적으로 접근해야할 때 두개의 포인터를 이용하여 합을 구하는 기법

O(N)으로 해결가능

 

1) a+b = k

시작점은 첫번째, 끝점은 마지막 원소를 가리킨 상태에서 시작.

이 경우는 정렬된 상태에서 진행이 필요하다.

start, end, result = 1, n-1, 0
while start < end:
    total = arr[start] + arr[end]
    if total > x:
        end-=1
    elif total < x:
        start+=1
    else:
        start+=1
        result+=1

3273번: 두 수의 합

 

2) start~end = k

시작점과 끝점이 첫번째 원소를 가리킨 상태에서 시작.

start, end, summary, result = 0, 0, 0, 0
for start in range(n):
    while summary < m and end < n:
        summary += data[end]
        end +=1
    if summary==m:
        result +=1
    summary -=data[start]

 

 

두 개의 포인터를 사용하여

 

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))
x = int(sys.stdin.readline())

start, end = 1,n-1
cnt = 0
while start < end:
    total = arr[start] + arr[end]
    if total < x:
        end-=1
    elif total > x:
        start+=1
    else:
        start+=1
        cnt+=1

print(cnt)