Trong bài toán này, chúng ta được cung cấp một mảng các giá trị nguyên và chúng ta phải in tất cả các mảng con đó từ mảng này có tổng bằng 0.
Hãy lấy một ví dụ để hiểu chủ đề tốt hơn,
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
Để giải quyết vấn đề này, chúng tôi sẽ kiểm tra tất cả các mảng con có thể. Và kiểm tra xem tổng của các mảng con này có bằng 0 hay không và in chúng ra. Giải pháp này rất dễ hiểu nhưng giải pháp phức tạp và độ phức tạp về thời gian của nó là O (n ^ 2) .
Một giải pháp tốt hơn cho vấn đề này là sử dụng Hashing. Để giải điều này, chúng ta sẽ tìm tổng nếu nó bằng 0, hãy thêm nó vào bảng Hash.
Thuật toán
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.
Ví dụ
#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;
} Đầu ra
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