1과 0이 같은 수의 부분 배열 계산


난이도 쉽게
자주 묻는 질문 시스코 쿠폰 Dunia Coursera 데이터 브릭 캐럿 SAP 연구소 테슬라
배열 해시

문제 정책

“1과 0이 같은 수의 하위 배열 개수”문제는 0과 1로만 구성된 배열이 제공된다는 것을 나타냅니다. 문제 설명은 0의 광고 1과 같지 않은 하위 배열의 개수를 알아 내도록 요청합니다.

arr[] = {0, 0, 1, 1, 0}
4

설명 : 모든 하위 배열은 (1,2), (3,4), (0,3), (1,4)입니다.

1과 0이 같은 수의 부분 배열 계산

 

arr[] = {1,0,0,1,1,0}
7

설명 : 모든 하위 배열은 (0, 1), (2,3), (0,3), (1,4), (0,5), (4,5), (2,5)입니다.

암호알고리즘

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

설명

0과 1로만 구성된 배열을 제공했습니다. 따라서 0과 1 만 포함하는 하위 배열의 개수를 알아 내야합니다. 우리는 사용할 것입니다 해싱. 우리는 지도. 맵에서 합계와 빈도를 1로 저장합니다. 맵에 새로 추가 된 경우 맵에 추가하고 그렇지 않으면 맵에있는 이전 합계 값의 빈도를 늘립니다.

그러나 그 전에 우리는 모든 0을 -1로 변환하고 루프를 순회하면서 배열 요소를 0으로 찾으면 -1로 변환합니다. 합계에 현재 배열 요소의 값을 더합니다. 합계를 확인하고 합계가 0이면 출력 값을 늘립니다. 이것은 모든 0을 -1로 변환하고 1과 0 만 있기 때문입니다. 따라서 0을 -1로 변환하고 그 값에 1을 더하면됩니다. 합계가 0 일 때마다 0과 1이 같을 때만 가능합니다.

1 개의 0과 0 개의 1이 있고 각각의 1을 -1로 변환하고 0 개의 0과 1 개의 -0을 더하면 0이 합산된다고 가정합니다. 이것은 또한 1을 -0로 변환 한 후 0을 합계로하려면 XNUMX과 XNUMX이 같아야 함을 의미합니다. 따라서 합계의 값을 XNUMX으로 찾을 때마다 출력 값을 증가시킵니다. 입력 배열을 고려하면 합계가 XNUMX이 될 때마다 출력 값을 업데이트합니다.

암호

1과 0이 같은 수의 하위 배열을 계산하는 C ++ 코드

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}
Sub-Arrays with equal 0's and 1's count is: 4

1과 0이 동일한 하위 배열을 계산하는 Java 코드

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}
Sub-Arrays with equal 0's and 1's count is:4

복잡성 분석

시간 C0mplexity

O (N) 어디에 "엔" 배열의 요소 수입니다. HashMap을 사용했기 때문에 선형 시간 복잡도를 달성 할 수 있습니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다. 여기 HashMap에서 합계를 키로 저장 했으므로 선형 공간 복잡성이 달성됩니다.