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

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

프로그래머스

 

[소스 코드]

// 23.06.21

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> answer;
    answer.push_back(1);
    answer.push_back(1000002);
    
    int i=0;
    int j=0;
    int sum=sequence[0];
    
    while (i <= j && j < sequence.size()){        
        if(sum >= k){ 
            if(sum == k){
                if(answer[1]-answer[0]>j-i){
                    answer[0]=i;
                    answer[1]=j;                
                }
                else if((answer[1]-answer[0])==(j-i) && i<answer[0]){
                    answer[0]=i;
                    answer[1]=j;                

                }
            }
            sum -= sequence[i];
            i++;
        }
        else{
            j++;
            sum += sequence[j];
        } 
    }
    
    return answer;
}

"투 포인터" 알고리즘을 이용해서 풀어야 했던 문제입니다.

i와 j값을 이중반복문으로 조절해가며 계산하면, 시간복잡도가 O(n^2)으로 너무 크기 때문에,

i와 j를 합계에 따라 잘 조절해가면서 계산하는 것이 포인트입니다.