2.打印给定数组中元素和为0的所有子数组

Dear 丶 2021-11-10 23:30 277阅读 0赞

给定整数数组，打印所有具有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\]

转载于:https://www.cnblogs.com/swifthua/p/7643435.html