[algorithm]twopointer

1 minute read

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를 만족해야한다.

Updated: