問題定義

n個の正の整数からなる配列と正の整数sが与えられたとき、要素の合計がs以上となる連続する部分配列のうち最小の長さを求める。条件を満たす部分配列が存在しない場合は0を返す。

例:
入力: s = 7, nums = [2,3,1,2,4,3]
出力: 2
説明: 部分配列[4,3]が条件を満たす最小長の連続部分配列

解法アプローチ

総当たり法

最も単純な方法は二重ループを用いた総当たり探索である。外側のループで開始位置を、内側のループで終了位置を決定し、各部分配列の合計がs以上かどうかを確認する。

void bruteForceMethod(int arrSize, int target, int elements[]) {
    int minLength = arrSize + 1;
    for (int start = 0; start < arrSize; start++) {
        int currentSum = elements[start];
        int currentLength = 1;
        for (int end = start + 1; end < arrSize; end++) {
            currentLength++;
            if (currentSum >= target && currentLength < minLength) {
                minLength = currentLength;
                break;
            }
            currentSum += elements[end];
        }
    }
    if (minLength == arrSize + 1) {
        cout << "最小長: 0" << endl;
    } else {
        cout << "最小長: " << minLength << endl;
    }
}

この方法の時間計算量はO(n²)となる。

スライディングウィンドウ法

より効率的な解法として、スライディングウィンドウ手法を用いる。二つのポインタ（左ポインタと右ポインタ）を使用し、ウィンドウ内の要素和が条件を満たすかどうかを動的に評価する。

void slidingWindowMethod(int target, int arrSize, int elements[]) {
    int minLength = arrSize + 1;
    int right = 0, left = 0, windowSum = 0;
    
    while (right < arrSize) {
        windowSum += elements[right++];
        while (windowSum >= target) {
            if (right - left < minLength) {
                minLength = right - left;
            }
            windowSum -= elements[left++];
        }
    }
    cout << "最小長: " << minLength << endl;
}

この手法の時間計算量はO(n)となる。

代替実装

減算をベースにした別の実装方法も存在する：

void alternativeWindowMethod(int target, int arrSize, int elements[]) {
    int minLength = arrSize + 1;
    int right = 0, left = 0;
    
    while (right < arrSize) {
        target -= elements[right++];
        while (target <= 0) {
            if (right - left < minLength) {
                minLength = right - left;
            }
            target += elements[left++];
        }
    }
    cout << "最小長: " << minLength << endl;
}