C++で合計がkに等しい最長部分配列の長さを求める方法

整数型の配列 nums と目標値 k が与えられたとき、要素の合計がちょうど k になる「部分配列(連続する要素の並び)」の中で最も長いものの長さを求める問題です。該当する部分配列がひとつも存在しない場合は、代わりに 0 を返します。

たとえば、入力が nums = [1, -1, 5, -2, 3]、k = 3 の場合、出力は 4 になります。これは、部分配列 [1, -1, 5, -2] の合計が 3 となり、条件を満たす中で最も長いためです。

解法のアプローチ

この問題は「累積和(プレフィックスサム)」とハッシュマップを組み合わせることで、O(n) の時間計算量で効率的に解けます。全ての部分配列を総当たりする O(n²) の素朴な方法よりも大幅に高速です。

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

• 答えを格納する変数 ret を 0 で初期化します。

• 累積和とそのインデックスを記録するためのマップ m を定義します。

• n := 配列 nums のサイズとします。

• 累積和 temp := 0 とし、m[0] := -1 として初期化します(配列の先頭より前の仮想的な位置を表します)。

• i を 0 から n-1 までループしながら、次の処理を行います。

  • temp に nums[i] を加算して累積和を更新します。

  • (temp − k) がマップ m に存在する場合、ret と i − m[temp − k] の大きい方を ret に代入します。

  • temp がまだマップ m に存在しない場合、m[temp] := i として現在のインデックスを登録します。

• 最後に ret を返します。

アルゴリズムのポイント

この手法の鍵は累積和の性質にあります。インデックス i までの累積和が temp であり、過去のある位置 j での累積和が temp − k だった場合、区間 (j, i] の要素の合計はちょうど k になります。したがって、m[temp − k] に記録されたインデックスとの差 i − m[temp − k] が、その時点で考えられる部分配列の長さとなります。

また、同じ累積和が複数回現れた場合は、最初に現れた(最も左側の)インデックスだけを保持します。開始位置が左にあるほど部分配列が長くなるため、これにより常に最長の候補を見つけられるようになっています。

実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxSubArrayLen(vector<int>& nums, int k) {
      int ret = 0;
      unordered_map <int, int> m;
      int n = nums.size();
      int temp = 0;
      m[0] = -1;
      for(int i = 0; i < n; i++){
         temp += nums[i];
         if(m.count(temp - k)){
            ret = max(ret, i - m[temp - k]);
         }
         if(!m.count(temp)){
            m[temp] = i;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,-1,5,-2,3};
   cout << (ob.maxSubArrayLen(v, 3));
}

入力

[1,-1,5,-2,3], 3

出力

4

計算量

時間計算量は O(n)、空間計算量は O(n) です。配列を一度走査するだけで済み、各ステップでマップへの参照・挿入は平均 O(1) で行えるため、大きな入力に対しても高速に動作します。