Tìm Tổng của tất cả tổng mảng con duy nhất cho một mảng nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm n giá trị nguyên. Nhiệm vụ của chúng ta là tìm tổng của tất cả tổng mảng con duy nhất cho một mảng nhất định . Tổng mảng con là tổng các phần tử của mảng con đã cho.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Giải thích -

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

Phương pháp tiếp cận giải pháp

Một giải pháp cho vấn đề là lưu trữ tổng của mảng con và sau đó sắp xếp chúng để tìm duy nhất một lần. Sau đó, chúng tôi sẽ xem xét tất cả các mảng con duy nhất cho tổng.

Thuật toán

Bước 1 - Tìm tổng của tất cả các mảng con và lưu trữ nó trong một vectơ.

Bước 2 - Sắp xếp các vectơ.

Bước 3 - Xem xét tất cả các vectơ là duy nhất và đánh dấu tổng phần còn lại là 0.

Bước 4 - Tính toán và in ra tổng.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The sum of all unique subarray sum is 144

Một cách tiếp cận khác sử dụng Lặp lại

Một cách tiếp cận khác để giải quyết vấn đề là sử dụng bảng băm. Chúng tôi sẽ tìm các tổng của mảng con và lưu trữ chúng trong một bảng băm và số lượng băm tăng dần. Sau đó, tìm tổng của tất cả các mảng con duy nhất (mảng con có số băm 1).

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

The sum of all unique subarray sum is 124