[algorithm]twopointer
Two Pointer
참고:link
연속되는 값들에서 특정한 합을 찾는 알고리즘
서브배열이나 리스트를 생성해서 계속 합을 구하지 않고 인덱스 값을 두 개 두어 불필요한 계산을 하지 않는다.
[1,2,3,4,5] 배열이 있고 합이 5를 찾는 경우 start = 0; end = 0;
[배열]
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
[TwoPointer]
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| start | – | – | – | – |
| end | – | – | – | – |
start와 end를 늘려가며 사이의 값들을 합한다.
start = 0, end= 0 이므로 sum = 1;
[TwoPointer]
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| start | end | – | – | – |
찾는값 5보다 작으므로 end를 1 증가
start = 0, end = 1 이므로 sum = 1 + 2 => 3;
[TwoPointer]
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| start | – | end | – | – |
찾는값 5보다 작으므로 end를 1 증가
start = 0, end = 2 이므로 sum = 1 + 2 + 3 => 6;
[TwoPointer]
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| – | start | end | – | – |
찾는값 5보다 크므로 start를 1 증가
start = 1, end = 2 이므로 sum = 2 + 3 => 5;
마지막으로 [TwoPointer]
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| – | – | – | – | start |
| – | – | – | – | end |
이 경우에 값 5를 찾을 수 있다.
- 배열이나 리스트에서 연속된 값들의 합을 구하는 경우 서브 배열을 두고 반복문으로
서브배열의 합을 구하는 경우 시간복잡도가 O(N^2)이지만 투 포인터를 이용하면
O(N)으로 해결할 수 있다. - start <= end를 만족해야한다.