在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: 创建sum变量。
Step 2: 如果sum=0，子数组从索引0开始到数组的结束索引。
Step 3: 如果当前总和在哈希表中。
Step 4: 如果总和存在，则从i+1到n的子数组必须为零。
Step 5: 否则插入到哈希表中。

示例

#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