打印总和为0的所有子数组


难度级别
经常问 亚马逊 免费收费 的确 信息边缘 微软 OYO房间
排列 哈希

给您一个整数数组,您的任务是打印sum等于0的所有可能的子数组。因此我们需要打印sum和0的所有子数组。

使用案列

打印总和为0的所有子数组

arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

算法

  1. 查找带有一些变量(例如“ Sum”)的数组元素的总和,以跟踪总和为0的子数组。
  2. If 总和 如果发现为0,则表示可能的子数组是从0到当前索引。
  3. 检查是否 总和 从上述过程中发现的,存在于我们的 地图位置 或没有。
  4. 如果map包含总和,则意味着它是前一个子数组的总和,现在它成为元素的总和,直到当前索引为止。
  5. 如果当前总和不存在,则将其插入到地图中。

说明

我们将使用 散列 因为这样,我们可以关注子数组及其索引。 另外,我们将使用不同的集合。 首先,我们必须找到数组中所有数字,这些数字构成可能的子数组,且总和为0。为此,我们将把数组中的元素相加并将其存储为sum。 开始时已经对总和进行了初始化。

我们将创建一个以临时总和为键,向量为值的地图。 因此,此处的矢量表示从输入开始的元素之和等于当前和的索引。

此后,我们开始遍历数组。 因此,随着前进,我们继续将元素添加到变量总和中。 如果 总和 在任何时候都被发现为0。 因此,这意味着从头开始的子数组为0。此外,如果找到了总和等于0的索引。

如果发现总和不为零。 然后,我们检查地图是否包含该总和。 如果地图不包含计算得出的总和。 然后,不存在任何以当前索引结尾并且总和为0的子数组。因此,在找到所有以当前索引结尾并且总和等于0的子数组之后,我们将把当前索引添加到向量中以当前总和为键的地图。

但是,如果Map包含总和,则意味着我们找到了一些具有相同总和的先前子数组。 然后,我们需要将该总和和索引的值相加。

然后,我们返回我们声明为向量的列表。 从那里开始,如果返回值的大小为0,则意味着我们发现没有其他输出可以打印。

C ++代码打印总和为0的所有子数组

#include<iostream>
#include<unordered_map>
#include<vector>

using namespace std;
vector< pair<int, int> > getSubArray(int arr[], int n)
{
  unordered_map<int, vector<int> > Map;
  vector <pair<int, int>> result;
  int sum = 0;
  for (int i = 0; i < n; i++)
  {
    sum += arr[i];
    if (sum == 0)
      result.push_back(make_pair(0, i));
        if (Map.find(sum) != Map.end())
    {
      vector<int> vec = Map[sum];
      for (auto val = vec.begin(); val != vec.end(); val++)
        result.push_back(make_pair(*val + 1, i));
    }
    Map[sum].push_back(i);
  }
  return result;
}
void print(vector<pair<int, int>> result)
{
  for (auto j= result.begin(); j != result.end(); j++)
    cout << "Sub-Array found from " << j->first << " index to " << j->second <<" index"<< endl;
}
int main()
{
    int arr[] = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
  vector<pair<int, int> > result = getSubArray(arr, n);
  if (result.size() == 0)
    cout << "No such Sub-array exists";
  else
    print(result);

  return 0;
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

Java代码打印总和为0的所有子数组

import java.util.*;
class Pair
{
    int start, end;
    Pair(int a, int b)
    {
        start = a;
        end = b;
    }
}
class printSubArray0Sum
{
    public static ArrayList<Pair> getSubArray(int[] arr, int n)
    {
        HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
        ArrayList<Pair> temp = new ArrayList<>();
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
                temp.add(new Pair(0, i));
            ArrayList<Integer> list = new ArrayList<>();
            if (map.containsKey(sum))
            {
                list = map.get(sum);
                for (int j = 0; j < list.size(); j++)
                {
                    temp.add(new Pair(list.get(j) + 1, i));
                }
            }
            list.add(i);
            map.put(sum, list);
        }
        return temp;
    }
    public static void print(ArrayList<Pair> result)
    {
        for (int i = 0; i < result.size(); i++)
        {
            Pair pair = result.get(i);
            System.out.println("Sub-Array found from "+ pair.start + " index to " + pair.end+" index");
        }
    }
    public static void main(String args[])
    {
        int[] arr = {-2, 4, -2, -1, 1, -3, 1, 5, 7, -11, -6};
        int n = arr.length;

        ArrayList<Pair> result = getSubArray(arr, n);
        if (result.size() == 0)
            System.out.println("No such Sub-array exists");
        else
            print(result);
    }
}
Sub-Array found from 0 index to 2 index
Sub-Array found from 0 index to 4 index
Sub-Array found from 3 index to 4 index
Sub-Array found from 1 index to 6 index
Sub-Array found from 4 index to 9 index

复杂度分析

时间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。