[알고리즘] - 투 포인터(Two pointers)

대표적인 투 포인터 알고리즘 문제를 풀어보았다.

예를 들어 [1,2,1,3,1,1,1,2]의 배열이 있으면 연속 부분의 합이 특정숫자 6이 되는 경우가 몇 번 있는지 구하는 프로그램이다.

function solution(m, arr) {
    let answer = 0,
    lt = 0,
    sum = 0;
    for (let rt = 0; rt < arr.length; rt++) {
      sum += arr[rt];
      if (sum === m) answer++;
      while (sum >= m) {
        sum -= arr[lt++];
        if (sum === m) answer++;
      }
	}
	return answer;
}

rt -> 배열의 길이만큼 반복해준다.

answer -> 연속 부분의 합이 특정수(m)과 같은 경우가 몇번인지 확인

sum -> arr[0]부터 차례대로 더해준다. 이때 특정 수(m)과 같으면 answer에 1씩 더한다. 만약 특정수보다 커지면 

sum에서 arr[lt]를 하나씩 빼주는데 sum보다 작아질때 까지 빼준다. 빼다가 특정수와 같으면 answer에 +1을 해준다. 

while문의 조건은 만약 arr=[1,1,1,2,4]이고 m이 6일때 다 더하면 9이다. 9에서 arr[0]부터arr[2]까지  빼주면 8,7,6이 된다. 

이러면 answer에 +1을 해주고 다시 arr[3]을 빼주면 4가 되서 while문을 벗어날 수 있다.