투 포인터

배열의 특정 구간을 연속적으로 처리하는 알고리즘이다.

배열에서 연속된 데이터 구간에서 처리하기를 원하거나, 정렬된 두 배열이 문제 조건에 있다면, 투포인터 알고리즘을 의심해봐야 한다.

🧐 알고리즘

1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.
2. 현재 부분 합이 M과 같다면, 카운트한다.
3. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다.
4. 현재 부분 합이 M 보다 크다면, start를 1 증가시킨다.
5. 모든 경우를 확인할 때까지 2~4 과정 반복

👨‍💻 소스

import java.util.*;

public class TwoPointer {
  
  public static void main(String[] args){
    
    int[] arr = {1, 2, 3, 2, 5};
    
    int count = 0;
    
    int end = 0;
    int sum = 0;
    
    for(int start = 0 ; start < arr.length ; start++) {
      
      while(sum < 5 && end < arr.length) {
        sum += arr[end];
        end += 1;
      }
      
      if(sum == 5) {
        count++;
      }
      
      sum -= arr[start];
    }
    
    System.out.println(count);
    
  }
}

🏅 관련 자료