原文：
给定一个数组，打印该数组中所有总和为 0 的子数组。
示例：
input: arr = [6, 3, -1, -3, 4, -2, 2,
4, 6, -12, -7]
output:
subarray found from index 2 to 4
subarray found from index 2 to 6
subarray found from index 5 to 6
subarray found from index 6 to 9
subarray found from index 0 to 10
相关文章：
一个简单的pg电子试玩链接的解决方案是一一考虑所有子数组，并检查每个子数组的总和是否等于 0。 该pg电子试玩链接的解决方案的复杂度为o(n ^ 2)。
更好的方法是使用哈希。
对数组中的每个元素执行以下操作：
-
保持到目前为止在变量中遇到的元素的总和（例如总和）。
-
如果当前总和为 0，则找到一个从索引 0 开始到索引当前索引结束的子数组。
-
检查哈希表中是否存在当前总和。
-
如果哈希表中已经存在当前总和，则表明该总和是某些子数组元素
arr[0] … arr[i]的总和，现在对于当前子数组arr[0] … arr[j]获得相同的总和，表示子数组arr[i 1] … arr[j]的总和必须为 0。 -
将当前总和插入哈希表。
以下是上述方法的模拟：
下面是上述方法的实现：
c
// c program to print all subarrays
// in the array which has sum 0
#include
using namespace std;
// function to print all subarrays in the array which
// has sum 0
vector< pair > findsubarrays(int arr[], int n)
{
// create an empty map
unordered_map > map;
// create an empty vector of pairs to store
// subarray starting and ending index
vector > out;
// maintains sum of elements so far
int sum = 0;
for (int i = 0; i < n; i )
{
// add current element to sum
sum = arr[i];
// if sum is 0, we found a subarray starting
// from index 0 and ending at index i
if (sum == 0)
out.push_back(make_pair(0, i));
// if sum already exists in the map there exists
// at-least one subarray ending at index i with
// 0 sum
if (map.find(sum) != map.end())
{
// map[sum] stores starting index of all subarrays
vector vc = map[sum];
for (auto it = vc.begin(); it != vc.end(); it )
out.push_back(make_pair(*it 1, i));
}
// important - no else
map[sum].push_back(i);
}
// return output vector
return out;
}
// utility function to print all subarrays with sum 0
void print(vector> out)
{
for (auto it = out.begin(); it != out.end(); it )
cout << "subarray found from index " <<
it->first << " to " << it->second << endl;
}
// driver code
int main()
{
int arr[] = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7};
int n = sizeof(arr)/sizeof(arr[0]);
vector > out = findsubarrays(arr, n);
// if we didn't find any subarray with 0 sum,
// then subarray doesn't exists
if (out.size() == 0)
cout << "no subarray exists";
else
print(out);
return 0;
}
java
// java program to print all subarrays
// in the array which has sum 0
import java.io.*;
import java.util.*;
// user defined pair class
class pair
{
int first, second;
pair(int a, int b)
{
first = a;
second = b;
}
}
public class gfg
{
// function to print all subarrays in the array which
// has sum 0
static arraylist findsubarrays(int[] arr, int n)
{
// create an empty map
hashmap> map = new hashmap<>();
// create an empty vector of pairs to store
// subarray starting and ending index
arraylist out = new arraylist<>();
// maintains sum of elements so far
int sum = 0;
for (int i = 0; i < n; i )
{
// add current element to sum
sum = arr[i];
// if sum is 0, we found a subarray starting
// from index 0 and ending at index i
if (sum == 0)
out.add(new pair(0, i));
arraylist al = new arraylist<>();
// if sum already exists in the map there exists
// at-least one subarray ending at index i with
// 0 sum
if (map.containskey(sum))
{
// map[sum] stores starting index of all subarrays
al = map.get(sum);
for (int it = 0; it < al.size(); it )
{
out.add(new pair(al.get(it) 1, i));
}
}
al.add(i);
map.put(sum, al);
}
return out;
}
// utility function to print all subarrays with sum 0
static void print(arraylist out)
{
for (int i = 0; i < out.size(); i )
{
pair p = out.get(i);
system.out.println("subarray found from index "
p.first " to " p.second);
}
}
// driver code
public static void main(string args[])
{
int[] arr = {6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7};
int n = arr.length;
arraylist out = findsubarrays(arr, n);
// if we did not find any subarray with 0 sum,
// then subarray does not exists
if (out.size() == 0)
system.out.println("no subarray exists");
else
print(out);
}
}
// this code is contributed by rachana soma
python3
# python3 program to print all subarrays
# in the array which has sum 0
# function to get all subarrays
# in the array which has sum 0
def findsubarrays(arr,n):
# create a python dict
hashmap = {}
# create a python list
# equivalent to arraylist
out = []
# tracker for sum of elements
sum1 = 0
for i in range(n):
# increment sum by element of array
sum1 = arr[i]
# if sum is 0, we found a subarray starting
# from index 0 and ending at index i
if sum1 == 0:
out.append((0, i))
al = []
# if sum already exists in the map
# there exists at-least one subarray
# ending at index i with 0 sum
if sum1 in hashmap:
# map[sum] stores starting index
# of all subarrays
al = hashmap.get(sum1)
for it in range(len(al)):
out.append((al[it] 1, i))
al.append(i)
hashmap[sum1] = al
return out
# utility function to print
# all subarrays with sum 0
def printoutput(output):
for i in output:
print ("subarray found from index "
str(i[0]) " to " str(i[1]))
# driver code
if __name__ == '__main__':
arr = [6, 3, -1, -3, 4, -2,
2, 4, 6, -12, -7]
n = len(arr)
out = findsubarrays(arr, n)
# if we did not find any subarray with 0 sum,
# then subarray does not exists
if (len(out) == 0):
print ("no subarray exists")
else:
printoutput (out)
# this code is contributed by vikas chitturi
c
// c# program to print all subarrays
// in the array which has sum 0
using system;
using system.collections.generic;
// user defined pair class
class pair
{
public int first, second;
public pair(int a, int b)
{
first = a;
second = b;
}
}
class gfg
{
// function to print all subarrays
// in the array which has sum 0
static list findsubarrays(int[] arr, int n)
{
// create an empty map
dictionary> map =
new dictionary>();
// create an empty vector of pairs to store
// subarray starting and ending index
list outt = new list();
// maintains sum of elements so far
int sum = 0;
for (int i = 0; i < n; i )
{
// add current element to sum
sum = arr[i];
// if sum is 0, we found a subarray starting
// from index 0 and ending at index i
if (sum == 0)
outt.add(new pair(0, i));
list al = new list();
// if sum already exists in the map there exists
// at-least one subarray ending at index i with
// 0 sum
if (map.containskey(sum))
{
// map[sum] stores starting index
// of all subarrays
al = map[sum];
for (int it = 0; it < al.count; it )
{
outt.add(new pair(al[it] 1, i));
}
}
al.add(i);
if(map.containskey(sum))
map[sum] = al;
else
map.add(sum, al);
}
return outt;
}
// utility function to print all subarrays with sum 0
static void print(list outt)
{
for (int i = 0; i < outt.count; i )
{
pair p = outt[i];
console.writeline("subarray found from index "
p.first " to " p.second);
}
}
// driver code
public static void main(string []args)
{
int[] arr = {6, 3, -1, -3, 4, -2,
2, 4, 6, -12, -7};
int n = arr.length;
list outt = findsubarrays(arr, n);
// if we did not find any subarray with 0 sum,
// then subarray does not exists
if (outt.count == 0)
console.writeline("no subarray exists");
else
print(outt);
}
}
// this code is contributed by rajput-ji
输出：
subarray found from index 2 to 4
subarray found from index 2 to 6
subarray found from index 5 to 6
subarray found from index 6 to 9
subarray found from index 0 to 10
本文由 aditya goel 提供。 如果您喜欢 geeksforgeeks 并希望做出贡献，则还可以使用 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 geeksforgeeks pg电子试玩链接主页上，并帮助其他 geeks。
如果发现任何不正确的地方，或者想分享有关上述主题的更多信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
