O(n) 투 포인터

O(n) 의 시간 복잡도를 갖는 알고리즘을 사용 해야 할때 자주 사용하는 방식인 투 포인터. 

start_index와 end_index 두개의 index를 사용하여 이동시키면서 원하는 값을 찾는 문제이다. 

 

 

[ 투 포인터 이동 원칙 ]

sum > N  : sum = sum - start_index; start_index++; 

sum < N : end_index++; sum = sum + end_index; 

sum == N : end_index++; sum = sum + end_index; count ++; 

 

[ 슈도코드 작성해보기 ]

int count = 1, sum = 1, start_index = 1, end_index = 1;

int N = 어떤 값  ; 

while (end_index != N) {

if (sum == N) { end_index++; sum = sum + end_index; count ++;   } 

else if (sum > N ) { sum = sum - start_index; start_index++;  }

else if ( sum < N ) {  end_index++; sum = sum + end_index;   } 

		}

count 출력하기