[Programmers] [투포인터] Lv 2. 연속된 부분 수열의 합

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

프로그래머스

 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    // 25.02.14
    int s = 0, e = 0;
    int sum = sequence[0]; // 부분 수열의 합
    int subLen = sequence.size() + 1; // 부분 수열의 길이
    pair<int, int> result; // 부분 수열의 시작 인덱스와 마지막 인덱스를 담은 객체

    while (s <= e && e < sequence.size()) {
        if (sum < k) sum += sequence[++e];
        else if (sum == k) {
            if (e - s + 1 < subLen) { // 길이가 더 짧은 수열이면
                subLen = e - s + 1;
                result = { s, e };
            }
            sum -= sequence[s++];
        }
        else sum -= sequence[s++];
    }

    return { result.first, result.second };
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/commit/0f5305c560f4c08a5c211a1179f2a160b5fb802d#diff-dddef437c2a94284a3b6daa4f4d3ec16e5b0d90f53e9c90ae14dbd4db3e4d43e

[level 2] Title: 연속된 부분 수열의 합, Time: 5.61 ms, Memory: 36.7 MB -Baekjo… · developeSHG/Algorithm-Baekjoon_Pro