C++で合計が0のすべてのサブ配列を出力します
この問題では、整数値の配列が与えられ、合計が0に等しいこの配列からすべてのサブ配列を出力する必要があります。
トピックをよりよく理解するために例を見てみましょう
Input: array = [-5, 0, 2, 3, -3, 4, -1] Output: Subarray with sum 0 is from 1 to 4. Subarray with sum 0 is from 5 to 7 Subarray with sum 0 is from 0 to 7
この問題を解決するために、可能なすべてのサブアレイをチェックします。そして、これらのサブ配列の合計が0に等しいかどうかを確認し、それらを出力します。このソリューションは理解しやすいですが、ソリューションは複雑であり、時間計算量は O（n ^ 2）のオーダーです。 。
この問題のより良い解決策は、ハッシュを使用することです。これを解決するために、0に等しい場合の合計を見つけて、ハッシュテーブルに追加します。
アルゴリズム
Step 1: Create a sum variable. Step 2: If sum =0, subarray starts from index 0 to end index of the array. Step 3: If the current sum is in the hash table. Step 4: If the sum exists, then subarray from i+1 to n must be zero. Step 5: Else insert into the hash table.
#include <bits/stdc++.h>
using namespace std;
vector< pair<int, int> > findSubArrayWithSumZero(int arr[], int n){
unordered_map<int, vector<int> >map;
vector <pair<int, int>> out;
int sum = 0;
for (int i = 0; i < n; i++){
sum += arr[i];
if (sum == 0)
out.push_back(make_pair(0, i));
if (map.find(sum) != map.end()){
vector<int> vc = map[sum];
for (auto it = vc.begin(); it != vc.end(); it++)
out.push_back(make_pair(*it + 1, i));
}
map[sum].push_back(i);
}
return out;
}
int main(){
int arr[] = {-5, 0, 2, 3, -3, 4, -1};
int n = sizeof(arr)/sizeof(arr[0]);
vector<pair<int, int> > out = findSubArrayWithSumZero(arr, n);
if (out.size() == 0)
cout << "No subarray exists";
else
for (auto it = out.begin(); it != out.end(); it++)
cout<<"Subarray with sum 0 is from "<<it->first <<" to "<<it->second<<endl;
return 0;
} 出力
Subarray with sum 0 is from 1 to 1 Subarray with sum 0 is from 0 to 3 Subarray with sum 0 is from 3 to 4 Subarray with sum 0 is from 0 to 6 Subarray with sum 0 is from 4 to 6
-
C++でのサイズKのM個の重複しないサブ配列の最大合計
問題の説明 配列と2つの数値MおよびKが与えられます。配列内で、サイズK（重複しない）の最大M個のサブ配列の合計を見つける必要があります。 （配列の順序は変更されません）。 Kはサブアレイのサイズ、Mはサブアレイの数です。配列のサイズはm*kより大きいと想定できます。配列の合計サイズがkの倍数でない場合は、最後の配列の一部を取得できます。 例 指定された配列が={2、10、7、18、5、33、0}の場合。 N =7、M =3、K =1の場合、サブセットは-であるため、出力は61になります。 {33, 18, 10} アルゴリズム presum配列を作成します。これには、指定された配列の
-
C++のすべてのサブシーケンスの合計を求めます
n個の要素を持つ配列Aがあるとします。配列のすべてのサブセットの合計の合計を見つける必要があります。したがって、配列がA =[5、6、8]の場合、-のようになります。 サブセット 合計 5 5 6 6 8 8 5,6 11 6,8 14 5,8 13 5,6,8 19 合計 76 配列にはn個の要素があるため、2n個のサブセット（空を含む）があります。はっきりと観察すると、各要素が2n〜1回発生していることがわかります 例 #include<iostream> #includ