Cho mảng số nguyên, in tất cả các mảng con có tổng bằng 0.
Ví dụ:
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
Cách đơn giản: Kiểm tra mọi mảng con O(n^2). Cách tốt hơn: Dùng Hashing (bảng băm).
Thuật toán Hashing
Bước 1: Tạo biến sum = 0. Bước 2: Nếu sum = 0, mảng con từ 0 đến i. Bước 3: Nếu sum đã có trong bảng băm, mảng con từ (index+1) đến i có tổng 0. Bước 4: Thêm sum vào bảng băm.
Chương trình minh họa
#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 << "Không có mảng con nào";
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;
}
Kết quả
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