투포인터 알고리즘

구현 코드만 간략하게 작성..(외우기 위해서 😂)

 

리스트에 순차적으로 접근해야 할 때 사용할 수 있습니다.

 

투 포인터 알고리즘 기본 포멧

int N = 5; // 데이터의 개수 N
int M = 5; // 찾고자 하는 부분 합 M
int[] data = {1,2,3,2,5};

int cnt = 0;
int interval_sum = 0;
int end = 0;

for(int start=0;start<N;start++){ // start를 차례대로 증가시키기

	while(interval_sum < M && end < N){ // end를 가능한 만큼 증가시키기
		interval_sum += data[end];
		end+=1;
	}

	if(interval_sum==M){ // 부분합이 M이면 카운트 증가
		cnt+=1;
	}
	interval_sum -= data[start]; // 이전 start위치 값 빼주기
}

System.out.println(cnt);