투포인터 알고리즘

Given an array of sorted integers, find two numbers such that they add up to a target number.

Questions to ask:

- What does my input look like?

- Will the sum cause integer overflow?

 

[0, 1, 2, 3, 4, 5]

- O(n^2) for loop 2개 쓰는 것 ➡️ Brue-Force approach

- O(N log N) 알고리즘: Sort and Scan, Scan through array and use binary search

- 만약에 array가 정렬되어 있다면, 항상 binary search를 쓸 수 있는지 체크해보기.

- O(N): array sorted 되어 있고, front와 back pointer를 써가면 한 번만에 모든 element 스캔 가능

 

관련 문제

Leet code 167

 

참고

Visual introduction Two Pointer Algorithm | Data Structure and Algorithm for Coding Interviews