[pro] 프로그래머스 level2 178870 연속된 부분 수열의 합 (c++) - 투포인터

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=cpp 

프로그래머스

 

[풀이]

투포인터를 이용해 풀 수 있다. 처음 low와 high 인덱스는 모두 0을 가리킨다.

배열을 누적해서 더해가며 sum이 k보다 작으면 high를 증가시켜 더하고, 커지면 현재 low가 가리키고 있는 값을 뺀 후 low를 증가시킨다. sum과 k가 같다면 더 짧은 부분 수열을 선택할 것이므로 길이를 비교해서 더 짧은 경우 갱신해준다.

 

[코드]

 

#include <iostream>
#include <string>
#include <vector>
#include <climits>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    //부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return
    int low = 0, high = 0;
    int minlen = INT_MAX;
    int sidx = 0, eidx = 0;
    int sum = sequence[low];
    while(low<=high){
        if(sum < k){
            high++;
            if(high==sequence.size()) break;
            sum += sequence[high];
        }
        else if(sum==k){
            if(minlen > (high-low)){
                minlen = high-low;
                sidx = low;
                eidx = high;
            }
            high++;
            if(high==sequence.size()) break;
            sum += sequence[high];
        }
        else{
            sum -= sequence[low];
            low++;
        }
    }
    
    answer.push_back(sidx);
    answer.push_back(eidx);
    return answer;
}