白俊解答-部分合わせて1806回

📜 理解问题

10000以下の自然数からなる長さNの数列.この数列の連続数の部分と中の和がSより大きく、最短の長さを求めるプログラムを作成してください.

💡 問題の再定義

数列の和がSの最短長より大きいことを求めます.

▼▼▼計画作成

2つの挿入法を用いてO(N)内で問題を解決できた.
startとendを0番目のインデックスから開始し、startとendの間の値の和がSより大きい場合は、それらが最も短い長さであることを確認します.次にstartをs以下に増やし、部分和を求める.startがendになり、最短の長さを出力するまで実行します.

💻 計画の実行

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, S, sum = 0, start = 0, end = 0, min_length = 100001;
    cin >> N >> S;
    vector<int> num(N+1);

    for (int i=0; i<N; i++) {
        cin >> num[i];
    }

    while (true) {
        if (sum >= S) {
            if (end - start < min_length) min_length = end - start;
            sum -= num[start];
            start += 1;
        }
        else {
            sum += num[end];
            if (end < N) end += 1;
            else {
                sum -= num[start];
                start += 1;
            }
        }
        if (start >= end) break;
    }
    min_length = min_length == 100001 ? 0 : min_length;
    cout << min_length;
    return 0;
}

🤔 振り返る

この問題は最初はBrootforceで解決したが,アルゴリズムはO(N)であった.²)そのためタイムアウトが発生しました.2つのポインタアルゴリズムで問題を解決してこそO(N)内で問題を解決できるのでBrootforceは使用できない.次のリンクは、2つのポインタアルゴリズムの説明です.
https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md