C++で合計がK以上となる最短の部分配列を求める方法

配列 A が与えられたとき、要素の合計が K 以上になる「最短の非空・連続する部分配列」の長さを求める問題を考えてみましょう。条件を満たす部分配列が存在しない場合は、-1 を返します。

たとえば、入力が [5, 3, -2, 2, 1]、K = 6 の場合、出力は 2 になります。これは先頭の 2 要素を取ると 5 + 3 = 8 ≥ 6 となり、条件を満たすためです。

解法のアプローチ

この問題は、累積和（プレフィックスサム）と単調両端キュー（deque）を組み合わせることで効率的に解けます。配列に負の数が含まれる場合、通常のスライディングウィンドウでは正しく判定できないため、deque を使って候補となるインデックスを管理するのがポイントです。

アルゴリズムの手順

• n := 配列 A のサイズとします。
• ans := n + 1、j := 0、sum := 0 で初期化します。
• 整数を格納する deque（dq）を用意します。
• i を 0 から n - 1 までループさせ、以下を実行します。
  • i > 0 の場合、A[i] := A[i] + A[i - 1] として累積和を作ります。
  • A[i] >= K ならば、ans := min(ans, i + 1) で答えを更新します（先頭からの部分配列が条件を満たすケース）。
  • dq が空でなく、A[i] - A[dq の先頭インデックス] >= K を満たす間、次を繰り返します。
    • ans := min(ans, i - dq.front()) で答えを更新します。
    • dq の先頭要素を削除します。
  • dq が空でなく、A[i] <= A[dq の末尾インデックス] を満たす間、dq の末尾要素を削除します（単調性を保つため）。
  • i を dq の末尾に追加します。
• 最後に、ans が n + 1 のままなら -1 を、そうでなければ ans を返します。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int shortestSubarray(vector<int> &A, int K) {
      int n = A.size();
      int ans = n + 1;
      int j = 0;
      int sum = 0;
      deque<int> dq;
      for (int i = 0; i < n; i++) {
         if (i > 0)
         A[i] += A[i - 1];
         if (A[i] >= K) {
            ans = min(ans, i + 1);
         }
         while (!dq.empty() && A[i] - A[dq.front()] >= K) {
            ans = min(ans, i - dq.front());
            dq.pop_front();
         }
         while (!dq.empty() && A[i] <= A[dq.back()])
         dq.pop_back();
         dq.push_back(i);
      }
      return ans == n + 1 ? -1 : ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,-2,2,1};
   cout << (ob.shortestSubarray(v, 6));
}

入力

{5,3,-2,2,1}, 6

出力

2

計算量について

このアルゴリズムの時間計算量は O(n) です。各インデックスは deque に対して高々 1 回追加され、1 回削除されるだけだからです。空間計算量も O(n) となります。累積和と単調 deque を使うことで、負の数を含む配列でも O(n²) の全探索よりもはるかに高速に最短部分配列を見つけられます。