Tìm xem có một mảng con có tổng bằng 0 trong C ++ hay không

Trong bài toán này, chúng ta được cung cấp một mảng arr [] có kích thước n gồm các giá trị nguyên. Nhiệm vụ của chúng ta là tìm xem có một mảng con có tổng bằng 0 hay không.

Chúng ta cần kiểm tra xem mảng đã cho có chứa mảng con mà tổng của tất cả các phần tử bằng 0.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: arr [] ={3, 1, -2, 1, 4, 5}

Đầu ra: Có

Giải thích:

Mảng con {1, -2, 1} có tổng tất cả các giá trị bằng 0.

Phương pháp tiếp cận giải pháp:

Một giải pháp đơn giản cho vấn đề bằng cách xem xét tất cả các mảng con và kiểm tra tổng của tất cả các phần tử bằng 0.

Một giải pháp khác cho vấn đề là sử dụng băm. Chúng ta cần lặp qua mảng và sau đó tìm tổng cho đến chỉ mục hiện tại và lưu trữ nó trong bảng băm.
Sau đó, kiểm tra trong bảng băm, nếu giá trị tổng giống như đã gặp trước đó, tìm thấy một mảng con có sum =0.

Nếu tìm thấy mảng con, hãy trả về True

Trả lại khác Sai

Chương trình minh họa cách giải quyết vấn đề của chúng tôi,

Ví dụ

#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;
}

Đầu ra

SubArray with sum equal to 0 exists in the array