Imprimir todos los subarreglos con suma 0

Dada una array, imprima todas las subarreglas en la array que tiene suma 0.

Ejemplos: 

C++

// C++ program to print all subarrays
// in the array which has sum 0
#include <bits/stdc++.h>
using namespace std;
  
// Function to print all subarrays in the array which
// has sum 0
vector< pair<int, int> > findSubArrays(int arr[], int n)
{
    // create an empty map
    unordered_map<int, vector<int> > map;
  
    // create an empty vector of pairs to store
    // subarray starting and ending index
    vector <pair<int, int>> 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<int> 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<pair<int, int>> 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<pair<int, int> > 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<Pair> findSubArrays(int[] arr, int n)
    {
            // create an empty map
            HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
 
            // create an empty vector of pairs to store
            // subarray starting and ending index
            ArrayList<Pair> 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<Integer> 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<Pair> 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<Pair> 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<Pair> findSubArrays(int[] arr, int n)
    {
        // create an empty map
        Dictionary<int, List<int>> map =
                   new Dictionary<int, List<int>>();
 
        // create an empty vector of pairs to store
        // subarray starting and ending index
        List<Pair> outt = new List<Pair>();
 
        // 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<int> al = new List<int>();
             
            // 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<Pair> 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<Pair> 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

Javascript

// JavaScript program to print all subarrays
// in the array which has sum 0
 
// Function to print all subarrays in the array which
// has sum 0
function findSubArrays(arr, n)
{
    // create an empty map
    let map = {};
  
    // create an empty vector of pairs to store
    // subarray starting and ending index
    let out = [];
  
    // Maintains sum of elements so far
    let sum = 0;
  
    for (var 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([0, i]);
  
        // If sum already exists in the map there exists
        // at-least one subarray ending at index i with
        // 0 sum
        if (map.hasOwnProperty(sum))
        {
            // map[sum] stores starting index of all subarrays
            let vc = map[sum];
            for (let it of vc)
                out.push([it + 1, i]);
        }
        else
            map[sum] = [];
  
        // Important - no else
        map[sum].push(i);
    }
  
    // return output vector
    return out;
}
  
// Utility function to print all subarrays with sum 0
function print(out)
{
    for (let it of out)
        console.log("Subarray found from Index " + it[0] + " to " + it[1]);
}
  
  
// Driver code
let arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7];
let n = arr.length;
  
let out = findSubArrays(arr, n);
  
// if we didn’t find any subarray with 0 sum,
// then subarray doesn’t exists
if (out.length == 0)
    console.log("No subarray exists");
else
    print(out);
 
// This code is contributed by phasing17.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *