[프로그래머스] 연속된 부분 수열의 합

 

다시 푸는 문제 !

마찬가지로 투포인터를 이용해 풀이할 수 있었다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int cmp(pair<int, int> a, pair<int, int> b) {
    int aLen = a.second - a.first;
    int bLen = b.second - b.first;
    if(bLen == aLen)
        return a.first < b.first;
    else
        return aLen < bLen;
}


vector<int> solution(vector<int> sequence, int k) {
    vector<pair<int, int>> answer;
    int result = 0;
    int j = 0;
    for(int i = 0; i < sequence.size(); i++) {
        while(result < k && j < sequence.size()) {
            result += sequence[j];
            j++;
        }
        if(result == k) {
            answer.push_back({i, j - 1});
        }
        result -= sequence[i];
    }
    sort(answer.begin(), answer.end(), cmp);

    return {answer[0].first, answer[0].second};
}