[알고리즘] Two Pointer

1. Two Pointer 란?

• 두 개의 포인터를 동시에 움직여가며 문제를 해결하는 알고리즘 입니다.
• 조건을 충족하는 한 쌍의 값을 찾는데 사용합니다.
• 정렬된 선형 데이터에서 사용됩니다.

 

특징

• 반복을 줄여 시간복잡도를 줄이는 목적을 가지는 알고리즘 입니다.

 

2. 사용 사례

Two Sum

• 배열 중 조건을 만족하는 숫자쌍 찾기

 

문제

• Two Sum 2 - Input Array is sorted (문제) (해설)

 

Sliding Window

• 조건에 만족하는 subarray 찾기
• 일정한 크기의 구간을 움직여 문제를 해결합니다.

 

문제

• Minimum Size Subarray Sum (문제) (해설)
• Longest Substring Without Repeating Characters (문제) (해설)

 

Fast / Slow

• 배열 내 중복 원소 확인하기
• 링크드리스트 내 사이클 확인하기

 

문제

• Linked List Cycle (문제) (해설)

 

 

 

 

출처

• [Median] tarun jain - Two Pointers