给定整数数组，打印所有具有0和的子数组
例如，
输入： {4,2,-3,-1,0,4}
具有0和的子阵列是:
{-3,-1,0,-4}
{0}
输入： {3，4，-7，3，1，3，1，-4，-2，-2}
具有0和的子阵列是
{3，4，-7}
{4，-7，3}
{-7，3，1，3}
{3，1，-4}
{3，1，3，1，-4，-2，-2}
{3，4，-7，3，1，3，1，-4，-2，-2}
方法一：
原始的方法是考虑所有的子阵列并找到它的存在。如果子阵列的和等于0，就打印它。初始解的时间复杂度为O(n^3),因为存在n^2个子阵列，并且需要O(n)个时间来占到其元素的和。该方法可以通过在恒定时间内计算子阵列和来优化在O(n^2)时间内运行。
c语言：
1 #include <iostream>
2 #include <unordered_map>
3 using namespace std;
4
5 void printallSubarrays(int arr[], int n)
6 {
7 for (int i = 0; i < n; i++)
8 {
9 int sum = 0;
10 for (int j = i; j < n; j++)
11 {
12 sum += arr[j];
13 if (sum == 0)
14 cout << "Subarray [" << i << ".." << j << "]/n";
15 }
16 }
17 }
18
19 int main()
20 {
21 int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
22 int n = sizeof(arr) / sizeof(arr[0]);
23
24 printallSubarrays(arr, n);
25
26 system("pause");
27 return 0;
28 }
java语言：
1 package 排列;
2
3 public class PrintallSubarrays1
4 {
5 public static void printallSubarrays(int arr[])
6 {
7 int n = arr.length;
8
9 for (int i = 0; i < n; i++)
10 {
11 int sum = 0;
12
13 for (int j = i; j < n; j++)
14 {
15 sum += arr[j];
16
17 if (sum == 0)
18 System.out.println("Subarray [" + i + ".." + j + "]");
19 }
20 }
21 }
22
23 public static void main (String[] args)
24 {
25 int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
26
27 printallSubarrays(arr);
28 }
29 }
输出：
Subarray [0..2]
Subarray [0..9]
Subarray [1..3]
Subarray [2..5]
Subarray [3..9]
Subarray [5..7]
方法二：
使用multimap打印给定数组中sum=0的所有子数组。创建一个空的多映射以存储具有给定和的所有子数组的结束索引。我们遍历给定的数组，并保持到目前为止所看到的元素总和。如果得到和之前，则存在至少一个子阵列，其中0和结束于当前索引，并且我们打印所有这些子阵列
c语言：
1 #include <iostream>
2 #include <unordered_map>
3 using namespace std;
4
5 void printallSubarrays(int arr[], int n)
6 {
7 // 创建一个空的multi-map来存储sub-arrays的结束索引
8 unordered_multimap<int, int> map;
9
10 //将（0，-1）对插入到集合中以处理子数组的情况
11 //和为0 从索引0开始
12 //pair 是 一种模版类型。每个pair 可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去
13 map.insert(pair<int, int>(0, -1));
14
15 int sum = 0;
16 for (int i = 0; i < n; i++)
17 {
18 sum += arr[i];
19
20 if (map.find(sum) != map.end())
21 {
22 //auto自动存储期。具有自动存储期的变量在进入声明该变量的程序块是被建立，它在该程序块活动时存在，退出该程序块时撤销
23 auto it = map.find(sum);
24
25 while (it != map.end() && it->first == sum)
26 {
27 cout << "Subarray [" << (it->second + 1) << ".." << i << "]/n";
28 it++;
29 }
30 }
31
32 map.insert(pair<int, int>(sum, i));
33 }
34 }
35
36 int main()
37 {
38 int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
39 int n = sizeof(arr) / sizeof(arr[0]);
40
41 printallSubarrays(arr, n);
42
43 return 0;
44 }
java语言：
1 package 排列;
2
3 import java.util.HashMap;
4 import java.util.Map;
5 import java.util.ArrayList;
6
7 public class PrintallSubarrays2{
8 @SuppressWarnings("all")
9 private static void insert(Map<Integer, ArrayList> hashMap,Integer key, Integer value) {
10 if (hashMap.containsKey(key))
11 hashMap.get(key).add(value);
12 else{
13 ArrayList<Integer> list = new ArrayList<Integer>();
14 list.add(value);
15 hashMap.put(key, list);
16 }
17 }
18
19 @SuppressWarnings("all")
20 public static void printallSubarrays(int arr[]){
21 int n = arr.length;
22 Map<Integer, ArrayList> hashMap = new HashMap<Integer, ArrayList>();
23 insert(hashMap, 0, -1);
24
25 int sum = 0;
26 for (int i = 0; i < n; i++){
27 sum += arr[i];
28 if (hashMap.containsKey(sum)){
29 ArrayList<Integer> list = hashMap.get(sum);
30 for (Integer value: list) {
31 System.out.println("Subarray [" + (value + 1) + ".." +
32 i + "]");
33 }
34 }
35 insert(hashMap, sum, i);
36 }
37 }
38
39 public static void main (String[] args){
40 int A[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
41 printallSubarrays(A);
42 }
43 }
输出：
Subarray [0..2]
Subarray [1..3]
Subarray [2..5]
Subarray [5..7]
Subarray [0..9]
Subarray [3..9]
原创文章，作者：Maggie-Hunter，如若转载，请注明出处：https://blog.ytso.com/15156.html