C ++で指定された合計のサブ配列を検索-（負の数を処理）

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

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

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

説明 −

Subarray sum = 5 - 1 + 4 + 6 = 14

ソリューションアプローチ

この問題の簡単な解決策は、ネストされたループを使用することです。配列をループし、内部ループを使用して、サブ配列を見つけます。サブアレイごとに、すべての要素の合計を見つけて、指定された合計値と比較します。等しい場合は、サブ配列を出力します。配列のすべての要素がトラバースされた場合、そのような配列は見つかりませんでした。

アルゴリズム

• ステップ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 = 14;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

出力

Subarray with given sum : { 5 -1 4 6 }

問題を解決するためのより良いアプローチは、ハッシュマップを使用することです。ハッシュマップは、現在のインデックスまでプレフィックスの合計を格納します。また、インデックスについては、sumを含むサブ配列が存在するかどうかを確認してください。 sum=sum--valueのプレフィックスがあるかどうかを確認します。

例

ソリューションの動作を説明するプログラム

#include <bits/stdc++.h>
using namespace std;
void printSubArray(int arr[], int i, int j){
   cout<<"{ ";
      for(; i <= j; i++)
      cout<<arr[i]<<" ";
   cout<<"}";
}
void findSubArrayWithSum(int arr[], int n, int sum) {
   unordered_map<int, int> map;
   int curr_sum = 0;
   for (int i = 0; i < n; i++){
      curr_sum = curr_sum + arr[i];
      if (curr_sum == sum) {
         cout<<"SubArray with the given sum :";
         printSubArray(arr, 0, i);
         return;
      }
      if (map.find(curr_sum - sum) != map.end()) {
         cout<<"SubArray with the given sum : ";
         printSubArray(arr, map[curr_sum - sum] + 1 , i);
         return;
      }
      map[curr_sum] = i;
   }
   cout<<"No subarray found!";
}
int main() {
   int arr[] = { 2, 5, -1, 4, 6, 9, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int sum = 14;
   findSubArrayWithSum(arr, n, sum);
   return 0;
}

出力

SubArray with the given sum : { 5 -1 4 6 }