투 포인터 (Two Pointers)

투 포인터 (Two Pointers) 란?

리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

• 완전 탐색으로 시간 복잡도 O(N^2) 걸릴 작업을 O(N)으로 줄여주는 효율적인 알고리즘

 

언제 사용되는가?

• 연속된 부분 배열의 합/곱을 구해야 할 때
• 정렬된 배열에서 특정 조건을 만족하는 두 수의 쌍을 찾을 때
• 병합 정렬처럼 두 개의 리스트를 합칠 때

 

 

예시 문제 풀이 : https://record47584.tistory.com/61

연속된 부분 수열의 합 (투포인터)