[알고리즘] 투 포인터 알고리즘

[개념]

 

 

 

구간 합을 구할 때 사용되는 알고리즘으로 배열의 길이가 짧은 경우 이중 for문을 사용해서 구하면 되지만

배열의 길이가 길어지면 시간 초과가 발생하므로 투 포인터 알고리즘을 사용한다.

 

 

아래 코드에서 보면  N은 배열의 크기,  M은 구하고자 하는 합이다.

구간의 합이 M을 만족하는 경우의 수를 구한다고 하자.

 

start, end 모두 배열의 첫번째부터 시작한다.

 

- M = sum

구간의 합이 M과 같다면 경우의 수 total에 1을 추가한다.

그리고 end를 한칸 뒤로 움직인다.

 

- M < sum

현재 구간의 합이 구하고자 하는 구간의 합보다 크다면 start를 1씩 증가시켜 주면서 구간의 범위를 좁혀준다.

이 때 start가 end보다 커지게 되는 경우 start, end를 같은 위치로 처리한다.

 

- M > sum

현재 구간의 합이 구하고자 하는 구간의 합보다 작다면 end를 한칸 뒤로 움직여 구간의 범위를 넓혀준다.

 

 

[코드]

 

    int start =0 ;
    int end =0;
    int sum =arr[0];
    
    while(start <= end && end < N)
    {
        if(sum < M) sum += arr[++end];
        else if( sum > M)
        {
            sum -= arr[start++];
            if( start > end && start <N){
                end=  start;
                sum= arr[start];
            }
        }
        else if (sum == M)
        {
            total++;
            sum += arr[++end];
        }
    }