# 打印總和為0的所有子數組

## 例

`arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}`
```Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index```

## 算法

1. 查找帶有一些變量（例如“ Sum”）的數組元素的總和，以跟踪總和為0的子數組。
2. If 總和 如果發現為0，則表示可能的子數組是從0到當前索引。
3. 檢查是否 總和 從上述過程中發現的，存在於我們的 地圖 或沒有。
4. 如果map包含總和，則意味著它是前一個子數組的總和，現在它成為元素的總和，直到當前索引為止。
5. 如果當前總和不存在，則將其插入到地圖中。

## C ++代碼打印總和為0的所有子數組

```#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
unordered_map<int, vector<int> > Map;
vector <pair<int, int>> result;
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
result.push_back(make_pair(0, i));
if (Map.find(sum) != Map.end())
{
vector<int> vec = Map[sum];
for (auto val = vec.begin(); val != vec.end(); val++)
result.push_back(make_pair(*val + 1, i));
}
Map[sum].push_back(i);
}
return result;
}
void print(vector<pair<int, int>> result)
{
for (auto j= result.begin(); j != result.end(); j++)
cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
int n = sizeof(arr)/sizeof(arr[0]);
vector<pair<int, int> > result = getSubArray(arr, n);
if (result.size() == 0)
cout << "No such Sub-array exists";
else
print(result);

return 0;
}
```
```Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index
```

## Java代碼打印總和為0的所有子數組

```import java.util.*;
class Pair
{
int start, end;
Pair(int a, int b)
{
start = a;
end = b;
}
}
class printSubArray0Sum
{
public static ArrayList<Pair> getSubArray(int[] arr, int n)
{
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
ArrayList<Pair> temp = new ArrayList<>();
int sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr[i];
if (sum == 0)
temp.add(new Pair(0, i));
ArrayList<Integer> list = new ArrayList<>();
if (map.containsKey(sum))
{
list = map.get(sum);
for (int j = 0; j < list.size(); j++)
{
temp.add(new Pair(list.get(j) + 1, i));
}
}
list.add(i);
map.put(sum, list);
}
return temp;
}
public static void print(ArrayList<Pair> result)
{
for (int i = 0; i < result.size(); i++)
{
Pair pair = result.get(i);
System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
}
}
public static void main(String args[])
{
int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
int n = arr.length;

ArrayList<Pair> result = getSubArray(arr, n);
if (result.size() == 0)
System.out.println("No such Sub-array exists");
else
print(result);
}
}
```
```Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index```

## 複雜度分析

### 時間複雜度

O（N） 哪裡 “ n” 是數組中元素的數量。

### 空間複雜度

O（N） 哪裡 “ n” 是數組中元素的數量。