백준 1806 / 부분합

이중포문을 사용하면 쉽게 풀릴 것 같지만 n의 최대값이 100000이라 시간초과가 무조건 발생한다.

이중포문을 사용하면 O(N^2)의 시간복잡도가 발생하지만

투 포인터스 알고리즘(Two Pointers Algorithm)을 사용하면 O(N)으로 줄일 수 있다.

https://naivep.tistory.com/52

코드

#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int arr[100000];
 
int main() {
 
    //freopen("Text.txt", "r", stdin);
    int n, m;
 
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
 
 
    int ans = 2000000000;
    int len = 0;
    
    int left = 0; 
    int right = 0;
    int sum = arr[0];
 
    while (left <= right && right < n) {
 
        if (sum < m) {
            if (right < n) {
                right += 1;
                sum += arr[right];
            }
        }
        else if (sum >= m) {
            len = right - left + 1;
            if (ans > len) {
                ans = len;
            }
 
            if (left <= right) {
                sum -= arr[left];
                left++;
            }
        }
    }
 
    if (ans == 2000000000) {
        cout << 0;
    }
    else {
        cout << ans;
    }
 
}