C ++で指定された合計-（非負の数）のサブ配列を検索します

この問題では、ソートされていない順序で格納されたN個の正の整数で構成される配列arr[]が与えられます。私たちのタスクは、指定された合計のサブ配列を見つけることです。 。

問題を理解するために例を見てみましょう

Input : arr[] = {2, 5, 1, 4, 6, 9, 5} sum = 11
Output : subarray = {1, 4, 6}

説明 −

Subarray sum = 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がsumより大きくなるまで要素を追加してwindowSumを更新します。つまり、if（windowSum windowSum =windowSum +arr[endIndex]。

  • ステップ1.2 − windowSumがsumより大きい場合は、要素を削除してウィンドウサイズを縮小します。つまり、while（windowSum windowSum =windowSum--arr[endIndex]。

  • ステップ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 }