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

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

프로그래머스

 

점진적으로 인덱스를 변경하면서 더하거나 빼거나 하는 해당 문제를 만나면 가장 먼저 떠올려야하는 알고리즘이 두포인터이다.

처음 인덱스 low, hi를 0으로 두고

 

k보다 sum이 크면 lo를 늘려 전체 값을 줄이고

k보다 sum이 작으면 hi를 늘려서 전체 값을 늘려서 정답을 갱신해나가면 된다.

 

여기서는 가장 짧아야하므로

정답 판정 근거에 길이를 넣으면 쉽게 코드를 구현할 수 있다. 

 

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

using namespace std;

int prefix[1000001];

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    answer.push_back(0);
    answer.push_back(1000000000);
    
    int lo = 0;
    int hi = 0;
    int sum = sequence[0];
    
    while(hi < sequence.size()) {
        if(sum == k) {
            if(answer[1] - answer[0] > hi - lo) {
                answer[0] = lo;
                answer[1] = hi;
            }
            
            
            
            sum -= sequence[lo];
            lo++;
            hi++;
            sum += sequence[hi];
        } else {
            if(sum > k) {
                sum -= sequence[lo];
                lo++;
            } else {
                hi++;
                sum += sequence[hi];
            }
        }
    }
    
    return answer;
}