C++で合計が指定値以上となる最短の連続部分配列を求める方法

問題概要

n個の要素からなる配列と正整数 s が与えられます。このとき、要素の合計が s 以上となる「連続する部分配列（サブアレイ）」の中で最も短いものの長さを求めてください。条件を満たす部分配列が存在しない場合は、0 を返します。

例えば、配列が [2,3,1,2,4,3]、目標値が 7 の場合、答えは 2 になります。これは部分配列 [4,3] の合計が 7 であり、条件を満たす中で最も短いためです。

解法のアプローチ：スライディングウィンドウ

この問題は「スライディングウィンドウ（双方向ポインタ）」と呼ばれる手法で効率的に解けます。ウィンドウの右端を順に広げながら、合計が条件を満たし続ける限り左端を縮めていくことで、各要素は高々2回しか走査されません。

具体的な手順は以下の通りです。

• ans := 0、n := 配列Aのサイズ、j := 0、sum := 0 と初期化する

• i を 0 から n − 1 まで繰り返す

  • sum := sum + A[i]

  • sum − A[j] >= K かつ j <= i の間、次を繰り返す

    • sum := sum − A[j]

    • j を 1 増やす

  • sum >= K である場合

    • ans == 0 または ans > (i − j + 1) ならば、ans := (i − j + 1)

• ans を返す

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minSubArrayLen(int K, vector<int>& A) {
        int ans = 0;
        int n = A.size();
        int j = 0;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum += A[i];
            while(sum - A[j] >= K && j <= i){
                sum -= A[j];
                j++;
            }
            if(sum >= K){
                if(ans == 0 || ans > (i - j + 1)) ans = (i - j + 1);
            }
        }
    return ans;
    }
};
main(){
    vector<int> v = {2,3,1,2,4,3};
    Solution ob;
    cout << ((ob.minSubArrayLen(7,v)));
}

入力

7
[2,3,1,2,4,3]

出力

2

計算量の評価

時間計算量は O(n)、空間計算量は O(1) です。ポインタ i と j はそれぞれ配列を一度しか進まないため、全体的に線形時間で処理が完了します。ブルートフォース（全探索）では O(n²) かかるところを、この手法により大幅に高速化できます。