합계가 0 인 모든 부분 배열 인쇄


난이도 하드
자주 묻는 질문 아마존 FreeCharge 과연 정보 가장자리 Microsoft 오요 룸
배열 해시

정수 배열이 주어졌고, 당신의 임무는 합계가 0 인 가능한 모든 하위 배열을 인쇄하는 것입니다. 따라서 우리는 합계가 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. 합계가 0 인 하위 배열을 추적하기 위해 일부 변수가 "Sum"이라고 말하는 배열 요소의 합계를 찾습니다.
  2. If 합계 0이면 0부터 현재 인덱스까지 하위 배열이 발견 될 수 있음을 의미합니다.
  3. 확인 합계 위의 과정에서 발견 된 것입니다. 지도 아니면 않습니다.
  4. 맵에 합계가 포함되어 있으면 이전 하위 배열의 총 합계였으며 이제 현재 인덱스까지 요소의 합계가됩니다.
  5. 현재 합계가 아직없는 경우 맵에 삽입합니다.

설명

우리는 사용할 것입니다 해싱 왜냐하면 이것으로 우리는 하위 배열과 그 인덱스를 주시 할 수 있기 때문입니다. 또한 다른 컬렉션을 사용할 것입니다. 먼저, 합계가 0 인 가능한 하위 배열을 형성하는 배열의 모든 숫자를 찾아야합니다.이를 위해 배열의 요소를 더하여 합계에 저장합니다. 합계는 처음에 이미 초기화되었습니다.

임시 합계를 키로, 벡터를 값으로 사용하는 맵을 생성합니다. 따라서 여기서 벡터는 입력 시작부터 요소의 합이 현재 합과 같은 인덱스를 나타냅니다.

그 후 배열을 탐색하기 시작합니다. 따라서 앞으로 나아가면서 변수 합계에 요소를 계속 추가합니다. 만약 합 언제든지 0 인 것으로 확인됩니다. 따라서 이것은 처음부터 하위 배열이 0이라는 것을 의미합니다. 또한 합계가 0 인 일부 인덱스를 발견 한 경우에도 마찬가지입니다.

합계가 0이 아닌 경우. 그런 다음지도에 해당 합계가 포함되어 있는지 확인합니다. 지도에 계산 된 합계가 포함되지 않은 경우. 그러면 현재 인덱스에서 끝나고 합계가 0 인 하위 배열이 없습니다. 따라서 현재 인덱스에서 끝나고 합계가 XNUMX 인 모든 하위 배열을 찾은 후 현재 인덱스를 벡터에 추가합니다. 현재 합계를 키로하는 맵

그러나 Map에 합계가 포함되어 있다면 동일한 합계를 가진 이전 하위 배열을 발견했음을 의미합니다. 그런 다음 그 합계와 지수의 값을 더해야합니다.

그리고 이로부터 벡터로 선언 한 목록을 반환합니다. 거기에서 반환 값의 크기가 0이면 다른 출력이 인쇄되지 않음을 의미합니다.

합계가 0 인 모든 하위 배열을 인쇄하는 C ++ 코드

#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

합계가 0 인 모든 하위 배열을 인쇄하는 Java 코드

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) 어디에 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.