C++で合計が0のサブ配列があるかどうかを調べます

この問題では、整数値で構成されるサイズnの配列arr[]が与えられます。私たちのタスクは、合計が0のサブ配列があるかどうかを見つけることです。

指定された配列に、すべての要素の合計が0に等しいサブ配列が含まれているかどうかを確認する必要があります。

問題を理解するために例を見てみましょう

入力： arr [] ={3、1、-2、1、4、5}

出力： はい

説明：

サブアレイ{1、-2、1}は、すべての値の合計が0になります。

ソリューションアプローチ：

すべてのサブ配列を検討し、すべての要素の合計をチェックすることによる問題の簡単な解決策は0に等しいです。

この問題のもう1つの解決策は、ハッシュを使用することです。 配列をループしてから、現在のインデックスまでの合計を見つけてハッシュテーブルに格納する必要があります。
次に、ハッシュテーブルをチェックして、合計値が以前に検出されたものと同じであるかどうか、合計=0のサブ配列が見つかります。

サブアレイが見つかった場合は、 Trueを返します。

それ以外の場合はFalse

問題の動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;

bool isSubArraySumZero(int arr[], int n) {
   
   unordered_set<int> sumHash;

   int currSum = 0;
   for (int i = 0 ; i < n ; i++) {
     
      currSum += arr[i];
      if (currSum == 0 || sumHash.find(currSum) != sumHash.end())
         return true;
      sumHash.insert(currSum);
   }
   return false;
}

int main() {
   
   int arr[] = { 3, 1, -2, 1, 4, 5 };
   int n = sizeof(arr)/sizeof(arr[0]);
   if (isSubArraySumZero(arr, n))
      cout<<"SubArray with sum equal to 0 exists in the array";
   else
      cout<<"No subarray exists";
   return 0;
}

出力

SubArray with sum equal to 0 exists in the array