C++で特定の配列のすべての一意のサブ配列の合計の合計を検索

この問題では、n個の整数値で構成される配列arr[]が与えられます。私たちのタスクは、特定の配列のすべての一意のサブ配列の合計を見つけることです。 。サブアレイの合計は、指定されたサブアレイの要素の合計です。

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

Input : arr[] = {1, 2, 4}
Output : 23

説明 −

All subarrays of the given array are :
(1), (2), (4), (1, 2), (2, 4), (1, 2, 4)
Sum of subarrays = 1 + 2 + 4 + (1+2) + (2+4) + (1+2+4) = 23

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

この問題の解決策は、サブ配列の合計を保存し、それらを並べ替えて一意のものを1回見つけることです。次に、合計のすべての一意のサブ配列を検討します。

アルゴリズム

ステップ1 −すべてのサブ配列の合計を見つけて、ベクトルに格納します。

ステップ2 −ベクトルを並べ替えます。

ステップ3 −一意であるすべてのベクトルを考慮し、残りの合計を0にマークします。

ステップ4 −合計を計算して印刷します。

例

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

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int i, j;
   long int sumArrayTill[n + 1] = { 0 };
   for (i = 0; i < n; i++)
      sumArrayTill[i + 1] = sumArrayTill[i] + arr[i];
   vector<long int> subArraySum;
   for (i = 1; i <= n; i++)
      for (j = i; j <= n; j++)
        subArraySum.push_back(sumArrayTill[j] - sumArrayTill[i - 1]);
   sort(subArraySum.begin(), subArraySum.end());
   for (i = 0; i < subArraySum.size() - 1; i++){
      if (subArraySum[i] == subArraySum[i + 1]) {
         j = i + 1;
         while (subArraySum[j] == subArraySum[i] && j < subArraySum.size()){
            subArraySum[j] = 0; j++;
         }
         subArraySum[i] = 0;
      }
   }
   long sum = 0;
   for (i = 0; i < subArraySum.size(); i++)
      sum += subArraySum[i];
   return sum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

出力

The sum of all unique subarray sum is 144

反復を使用する別のアプローチ

この問題を解決する別のアプローチは、ハッシュテーブルを使用することです。サブアレイの合計を見つけてハッシュテーブルに格納し、ハッシュカウントをインクリメントします。次に、すべての一意のサブアレイ（ハッシュカウントが1のサブアレイ）の合計を求めます。

例

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

#include <bits/stdc++.h>
using namespace std;
long int findSumOfSubArraySum(int arr[], int n){
   int sumSubArraySum = 0;
   unordered_map<int, int> sumSubArray;
   for (int i = 0; i < n; i++) {
      int sum = 0;
      for (int j = i; j < n; j++) {
         sum += arr[j];
         sumSubArray[sum]++;
      }
   }
   for (auto itr : sumSubArray)
      if (itr.second == 1)
         sumSubArraySum += itr.first;
      return sumSubArraySum;
}
int main(){
   int arr[] = { 1, 2, 4, 7, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The sum of all unique subarray sum is "<<findSumOfSubArraySum(arr, n);
   return 0;
}

出力

The sum of all unique subarray sum is 124