打印總和為0的所有子數組


難度級別
經常問 亞馬遜 免費收費 確實 信息邊緣 Microsoft微軟 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” 是數組中元素的數量。