C++で指定した合計値を持つ部分配列を検索する方法（非負の数）

この問題では、N個の正の整数がソートされていない状態で格納された配列 arr[] が与えられます。私たちの課題は、指定された合計値と一致する部分配列を見つけることです。

問題を理解するための例

入力 : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
出力 : 部分配列 = {1, 4, 6}

説明 −

部分配列の合計 = 1 + 4 + 6 = 11

解法アプローチ①：ネストしたループを使う単純な方法

最もシンプルな解決策は、ネストしたループ（二重ループ）を使用する方法です。外側のループで配列を走査し、内側のループで各開始位置から考えられるすべての部分配列を生成します。それぞれの部分配列について要素の合計を計算し、指定された合計値と比較します。一致していればその部分配列を出力します。配列全体を走査しても見つからない場合は、「該当する部分配列は存在しない」と出力します。

アルゴリズム

• ステップ1 − 配列を i → 0 から (n-1) までループで走査します。

  • ステップ1.1 − 各要素について、可能なすべての部分配列の合計を求めます。

  • ステップ1.2 − 現在の部分配列の合計が指定された合計値と等しい場合、その部分配列を出力します。

• ステップ2 − 配列全体を走査しても部分配列が見つからない場合は、「指定された合計を持つ部分配列は見つかりませんでした！」と出力します。

コード例

この解法の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
    cout<<"{";
       for(; i < j; i++)
       cout<<arr[i]<<" ";
    cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
    int currSum;
    for (int i = 0; i < n; i++) {
        currSum = arr[i];
        for (int j = i + 1; j <= n; j++) {
            if (currSum == sum) {
            cout<<"Subarray with given sum : ";
            printSumArray(arr, i, j); return 1;
         }
         if (currSum > sum || j == n)
         break;
         currSum = currSum + arr[j];
      }
   }
   cout<<"No subarray found";
   return 0;
}
int main() {
   int arr[] = { 2, 5, 1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

出力

Subarray with given sum : { 1 4 6 }

解法アプローチ②：可変サイズのスライディングウィンドウを使う効率的な方法

より効率的な解決策は、スライディングウィンドウに似た手法ですが、ここではウィンドウサイズが可変である点が異なります。配列の最初の要素から開始し、合計が指定された値を超えるまで要素をウィンドウに追加していきます。合計が指定値を超えたら、再び合計が指定値以下になるまで先頭側の要素を取り除きます。この処理を配列全体を走査し終えるまで繰り返します。

処理中のどの時点でも、ウィンドウ内の合計が指定された合計値と一致すれば、その部分配列を出力します。また、配列の走査が完了しても合計が一致するウィンドウが見つからなかった場合は、「該当する部分配列は見つかりませんでした！」と出力します。

アルゴリズム

初期化 − windowSum = 0、sindex = 0、endindex = 0

• ステップ1 − endindex を使って配列を走査します。

  • ステップ1.1 − windowSum が合計値を超えるまで要素を加算して更新します。つまり、if(windowSum < sum) → windowSum = windowSum + arr[endIndex]。

  • ステップ1.2 − windowSum が合計値より大きい場合、要素を取り除いてウィンドウサイズを縮小します。つまり、while(windowSum > sum) → windowSum = windowSum - arr[startIndex]。

  • ステップ1.3 − windowSum == sum の場合、部分配列を出力します。

• ステップ2 − 配列の走査が完了した場合は、「不可能」を出力します。

コード例

この解法の動作を示すプログラムです。

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
    cout<<"{ ";
       for(; i < j; i++)
       cout<<arr[i]<<" ";
    cout<<"}";
}
int findSubArrayWithSum(int arr[], int n, int sum) {
    int windowSum = arr[0], startIndex = 0, endIndex;
    for (endIndex = 1; endIndex <= n; endIndex++) {
        while (windowSum > sum && startIndex < endIndex - 1) {
         windowSum -= arr[startIndex];
         startIndex++;
      }
      if (windowSum == sum) {
         cout << "Subarray with given sum : ";
         printSumArray(arr, startIndex ,endIndex);
         return 1;
      }
      if (endIndex < n)
      windowSum += arr[endIndex];
   }
   cout << "No subarray found";
   return 0;
}
int main() {
   int arr[] = { 2, 5, 1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 11;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

出力

Subarray with given sum : { 1 4 6 }

このように、非負の整数のみで構成される配列の場合、可変サイズのスライディングウィンドウを利用することで、二重ループによる総当たりよりも効率的に目的の部分配列を見つけることができます。