연속된 부분 수열의 합

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

프로그래머스

먼저 문제를 읽었을 때, 각 구간의 값을 구하면 되겠다는 생각을 하게 되었다.

그래서 아래처럼 구하려고 했다. 구간 값에 현재 값을 더해서 구하는 방식

[ 1 2 3 4 5 ], k = 7

1  2  3  4  5
   3  5  9  12
       6  10 15
               ...

시간 초과가 발생했다. 어디가 느릴까?
작성한 예시에서 보면 삼각형을 형태를 이루어지는 것을 볼 수 있다. for문 2개로 O(n2)의 시간 복잡도를 가짐을 볼 수 있다.

문제에서 주어진 입력을 한번 볼까?
   5 ≤ sequence의 길이 ≤ 1,000,000
길이가 10^6으로 O(n2)으로 구하면 시간 초과가 발생할 수 있다.

그러면 시간 복잡도를 낮춰야할 건데 어떻게 낮출까?

two pointer란 방법으로 하면 된다. O(n)으로 구할 수 있다.

이 문제에서 최소 길이의 구간을 구하는 것이니 for문으로 돌면서 최소 길이 구간을 만날 때마다 구간을 업데이트하면 된다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(vector<int> sequence, int k) {
    vector<int> ans;
    
    int i = 0, j = 0;
    int sum = sequence[i];
    while(i < sequence.size() ) {
        if(sum == k) {
            if(ans.size() == 0) {
                ans = {i , j};   
            } else {
                int temp = ans[1] - ans[0];
                if(j - i < temp) {
                    ans = { i, j };
                }
            }
            sum -= sequence[i++];
        } else if(sum < k && j + 1< sequence.size()) {
            sum += sequence[++j];
        // } else if(sum > k) {
        } else {
            sum -= sequence[i++];
        }
    }
    
    return ans;
}