นับ subarrays ด้วยจำนวน 1 และ 0 เท่ากัน


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ซิสโก้ คูปอง Coursera Databricks การัต SAP Labs เทสลา
แถว กัญชา

คำชี้แจงปัญหา

ปัญหา“ นับ subarrays ด้วยจำนวน 1 และ 0 เท่ากัน” ระบุว่าคุณได้รับอาร์เรย์ที่ประกอบด้วย 0 และ 1 เท่านั้น คำสั่งปัญหาขอให้ค้นหาจำนวนอาร์เรย์ย่อยที่มีจำนวนเท่ากับ 0 ของโฆษณา 1

ตัวอย่าง

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

คำอธิบาย: อาร์เรย์ย่อยทั้งหมดคือ (1,2), (3,4), (0,3), (1,4)

นับ subarrays ด้วยจำนวน 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 เท่านั้น เรากำลังจะใช้ hashing. เราจะประกาศก แผนที่. ในแผนที่เราจะจัดเก็บผลรวมและความถี่เป็น 1 หากเป็นแผนที่ใหม่ให้เพิ่มลงในแผนที่มิฉะนั้นจะเพิ่มความถี่ของค่าผลรวมก่อนหน้านี้ที่มีอยู่ในแผนที่

แต่ก่อนหน้านั้นเราจะแปลง 0 ทั้งหมดเป็น -1 ในขณะที่ข้ามลูปถ้าเราพบองค์ประกอบอาร์เรย์เป็น 0 เราจะแปลงเป็น -1 การเพิ่มค่าขององค์ประกอบอาร์เรย์ปัจจุบันให้กับผลรวม เราจะตรวจสอบผลรวมหากผลรวมเท่ากับ 0 เราจะเพิ่มมูลค่าของผลลัพธ์ นี่เป็นเพราะเรากำลังแปลง 0 ทั้งหมดเป็น -1 และเรามี 1 และ 0 เท่านั้น ดังนั้นเมื่อเราแปลง 0 เป็น -1 และเพิ่มค่านั้นด้วย 1s เมื่อใดก็ตามที่ผลรวมเป็น 0 จะเป็นไปได้ก็ต่อเมื่อเรามี 0 และ 1 เท่ากัน

สมมติว่าเรามี 1 สามสามตัวและ 0 สามตัวและการแปลง 0 แต่ละตัวเป็น -1 และบวกสาม 1 และสาม -1 เราจะได้ 0 เป็นผลรวม นอกจากนี้ยังบอกเป็นนัยว่าหลังจากแปลง 0 เป็น -1 เพื่อให้มี 0 เป็นผลรวมเราควรมีค่าเท่ากับ 0 และ 1 ดังนั้นเมื่อใดก็ตามที่คุณพบค่าของผลรวมเป็น 0 เราจะเพิ่มค่าผลลัพธ์ เมื่อพิจารณาถึงอาร์เรย์อินพุตเราจะอัปเดตค่าของเอาต์พุตเมื่อใดก็ตามที่เราได้รับผลรวมเป็น 0

รหัส

รหัส C ++ เพื่อนับ subarrays ที่มีจำนวนเท่ากับ 1 และ 0

#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

โค้ด Java เพื่อนับ subarrays ด้วยจำนวน 1 และ 0 เท่ากัน

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) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราใช้ HashMap เราจึงสามารถบรรลุความซับซ้อนของเวลาเชิงเส้นได้

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ ที่นี่ใน HashMap เราได้บันทึกผลรวมเป็นคีย์ดังนั้นจึงได้ความซับซ้อนของพื้นที่เชิงเส้น