2.打印给定数组中元素和为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语言：

#include <iostream>
#include <unordered_map>
using namespace std;

void printallSubarrays(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            if (sum == 0)
                cout << "Subarray [" << i << ".." << j << "]
";
        }
    }
}

int main()
{
    int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printallSubarrays(arr, n);

    system("pause");
    return 0;
}

 

　　java语言：

package 排列;

public class PrintallSubarrays1
{
    public static void printallSubarrays(int arr[])
    {
        int n = arr.length;

        for (int i = 0; i < n; i++)
        {
            int sum = 0;
     
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
     
                if (sum == 0)
                    System.out.println("Subarray [" + i + ".." + j + "]");
            }
        }
    }

    public static void main (String[] args)
    {
        int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };

        printallSubarrays(arr);
    }
}

 

 输出：

　　Subarray [0..2]
　　Subarray [0..9]
　　Subarray [1..3]
　　Subarray [2..5]
　　Subarray [3..9]
　　Subarray [5..7]

 

方法二：
　　使用multimap打印给定数组中sum=0的所有子数组。创建一个空的多映射以存储具有给定和的所有子数组的结束索引。我们遍历给定的数组，并保持到目前为止所看到的元素总和。如果得到和之前，则存在至少一个子阵列，其中0和结束于当前索引，并且我们打印所有这些子阵列

　　c语言：

#include <iostream>
#include <unordered_map>
using namespace std;

void printallSubarrays(int arr[], int n)
{
    // 创建一个空的multi-map来存储sub-arrays的结束索引
    unordered_multimap<int, int> map;

    //将（0，-1）对插入到集合中以处理子数组的情况
    //和为0 从索引0开始
    //pair 是 一种模版类型。每个pair 可以存储两个值。这两种值无限制。也可以将自己写的struct的对象放进去
    map.insert(pair<int, int>(0, -1)); 

    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum += arr[i];

        if (map.find(sum) != map.end())
        {
            //auto自动存储期。具有自动存储期的变量在进入声明该变量的程序块是被建立，它在该程序块活动时存在，退出该程序块时撤销
            auto it = map.find(sum); 

            while (it != map.end() && it->first == sum)
            {
                cout << "Subarray [" << (it->second + 1) << ".." << i << "]
";
                it++;
            }
        }

        map.insert(pair<int, int>(sum, i));
    }
}

int main()
{
    int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printallSubarrays(arr, n);

    return 0;
}

 　　java语言：

package 排列;

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;

public class PrintallSubarrays2{
    @SuppressWarnings("all")
    private static void insert(Map<Integer, ArrayList> hashMap,Integer key, Integer value) {
        if (hashMap.containsKey(key))
            hashMap.get(key).add(value);
        else{
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(value);
            hashMap.put(key, list);
        }
    }

    @SuppressWarnings("all")
    public static void printallSubarrays(int arr[]){
        int n = arr.length;
        Map<Integer, ArrayList> hashMap = new HashMap<Integer, ArrayList>();
        insert(hashMap, 0, -1);
        
        int sum = 0;
        for (int i = 0; i < n; i++){
            sum += arr[i];
            if (hashMap.containsKey(sum)){
                ArrayList<Integer> list = hashMap.get(sum);
                for (Integer value: list) {
                    System.out.println("Subarray [" + (value + 1) + ".." + 
                                                    i + "]");
                }
            }
            insert(hashMap, sum, i);
        }
    }

    public static void main (String[] args){
        int A[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
        printallSubarrays(A);
    }
}

输出：

　　Subarray [0..2]
　　Subarray [1..3]
　　Subarray [2..5]
　　Subarray [5..7]
　　Subarray [0..9]
　　Subarray [3..9]