[Algorithm] Programmers :: 연속된 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

vector<int> solution(vector<int> sequence, int k) 
{
    vector<int> answer(2);
 
    int left = 0;
    int right = 0;
    int minLength = 10000000;
    int curLength = 1;
    int sum = sequence[0];
 
    while (left <= right)
    {
        if (sum == k)
        {
            if (curLength < minLength)
            {
                minLength = curLength;
                answer[0] = left;
                answer[1] = right;
            }
        }
 
        if (sum < k)
        {
            if (right + 1 < sequence.size())
            {
                ++right;
                ++curLength;
                sum += sequence[right];
            }
            else break;
        }
        else
        {
            sum -= sequence[left];
            ++left;
            --curLength;
        }
    }
 
    return answer;
}

투포인터 예제로 자주나오는 유형의 문제이다.

최소의 수열길이는 1이기 때문에 두개의 포인터 left,right를 둘 다 0부터 시작한다.

주어지는 sequence는 비내림차순, 즉 오름차순이기 때문에 right를 한칸올리면 값을 늘릴 수 있고 left를 한칸올리면 값을 줄일 수 있다.

 

반복문탈출조건은 left <= right 인데, 이걸 만족시키기 위해서 sum < k일때 right값이 더이상 올라갈 수 없으면(끝인덱스에 도달했으면) 바로 반복문을 종료한다. 더이상 k값을 만족시킬 연속부분수열이 존재할 수 없기 때문이다.

아니면 그냥 최대 2N번정도만 수행하기 때문에, 해당회수만큼만 진행시키고 끝나면 종료시켜도 된다.