C++에서 합계가 0인 하위 배열이 있는지 찾기

이 문제에서는 정수 값으로 구성된 n 크기의 배열 arr[]이 제공됩니다. 우리의 임무는 합계가 0인 하위 배열이 있는지 찾는 것입니다.

주어진 배열에 모든 요소의 합이 0인 하위 배열이 포함되어 있는지 확인해야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력: arr[] ={3, 1, -2, 1, 4, 5}

출력: 예

설명:

하위 배열 {1, -2, 1}은 모든 값의 합이 0입니다.

해결 방법:

모든 하위 배열을 고려하고 모든 요소의 합이 0인지 확인하여 문제에 대한 간단한 솔루션입니다.

문제에 대한 또 다른 해결책은 해싱을 사용하는 것입니다. 배열에 대해 루프를 실행한 다음 현재 인덱스까지 합계를 찾아 해시 테이블에 저장해야 합니다.
그런 다음 해시 테이블을 확인하여 합계 값이 이전에 발생한 것과 같으면 합계 =0인 하위 배열이 발견됩니다.

하위 배열이 발견되면 True 를 반환합니다.

그렇지 않으면 거짓을 반환합니다.

문제의 작동 방식을 설명하는 프로그램

예

#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