資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告