数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在 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** - 找到所有子数组的和并将其存储在一个向量中。
**步骤 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
更新于: 2022-01-25
633 次查看
广告