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

프로그래머스

 

 

1. 길이가 짧은 수열을 구하기 위한 minLen, 합을 구하기 위한 sum, 시작 인덱스를 구하기 위한 startIdx를 선언

2. startIdx부터 시작해서 i까지 sequence[i], sequence[i -1]...을 더하므로 i가 endIdx의 역할을 함

3. 계속해서 더해가다 sum이 k보다 커지면 부분 수열의 시작 인덱스부터 뺌 <= 이에 따라 startIdx가 증가

4. 만약 sum == k이고 i - startIdx의 값이 minLen 보다 작다면 minLen의 값을 갱신하고 startIdx와 i를 answer에 담음

5. 모든 반복이 끝난 뒤 answer 리턴

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer(2, 0);
    int minLen = 1000001, sum = 0, startIdx = 0;
    
    for(int i = 0; i < sequence.size(); i++) {
        sum += sequence[i];
        
        while(sum > k) {
            sum -= sequence[startIdx++];
        }
        
        if(sum == k && i - startIdx < minLen) {
            minLen = i - startIdx;
            
            answer[0] = startIdx;
            answer[1] = i;
        }
    }
    
    return answer;
}