ช่วงที่ยาวที่สุดที่มีผลรวมเท่ากันในสองอาร์เรย์ไบนารี II  


ระดับความยาก กลาง
ถามบ่อยใน แอคเซนเจอร์ ซิสโก้ จริง คูลิซา SAP Labs Yandex
แถว กัญชา hashing

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

ในปัญหา“ ช่วงที่ยาวที่สุดที่มีผลรวมเดียวกันในสองอาร์เรย์ไบนารี II” เราได้กำหนดสองไบนารี อาร์เรย์ “ a” และ“ b” ที่มีขนาดเท่ากัน เขียนโปรแกรมเพื่อพิมพ์ช่วงที่ยาวที่สุดด้วยผลรวมเดียวกันในสองอาร์เรย์ สิ่งนี้สามารถอธิบายได้อย่างชัดเจนในตัวอย่างด้านล่าง

รูปแบบการป้อนข้อมูล  

บรรทัดแรกและบรรทัดเดียวที่มีค่าจำนวนเต็ม n

บรรทัดที่สองประกอบด้วย n ค่าที่คั่นด้วยช่องว่าง (0 หรือ 1) ของ“ a”

บรรทัดที่สามยังมี n ค่าที่คั่นด้วยช่องว่าง (o หรือ 1) ของ“ b”

รูปแบบผลลัพธ์  

บรรทัดแรกและบรรทัดเดียวที่มีค่าจำนวนเต็มซึ่งหมายถึงช่วงที่ยาวที่สุดโดยมีผลรวมเดียวกันในสองอาร์เรย์

ข้อ จำกัด  

  • 1 <= n <= 10 ^ 6
  • a [i], b [i] ต้องเป็น 0 หรือ 1

ตัวอย่าง  

4
0 1 0 1
1 0 0 0
3

คำอธิบาย: ในตัวอย่างข้างต้นจากดัชนี 0 ถึง 3 ผลรวมขององค์ประกอบจากดัชนี 0 ถึง 3 ในสองอาร์เรย์จะเหมือนกัน

อัลกอริทึมสำหรับช่วงที่ยาวที่สุดที่มีผลรวมเดียวกันในสองอาร์เรย์ไบนารี II  

การปรับใช้ตรรกะเป็นไปตามข้อสังเกตด้านล่าง

  • เนื่องจากมีทั้งหมด n องค์ประกอบผลรวมสูงสุดคือ n สำหรับทั้งสองอาร์เรย์
  • ความแตกต่างระหว่างผลรวมสองจำนวนแตกต่างกันไป -n ไปยัง n. ดังนั้นจึงมีค่าความแตกต่างทั้งหมด 2n + 1 ที่เป็นไปได้
  • หากความแตกต่างระหว่างผลรวมคำนำหน้าของอาร์เรย์สองอาร์เรย์เหมือนกันที่จุดสองจุดดังนั้นเรย์ย่อยระหว่างสองจุดนี้จะมีผลรวมเท่ากัน
ดูสิ่งนี้ด้วย
การนับคู่หาร

ตอนนี้เมื่อพิจารณาจากสามจุดข้างต้นจะย้ายไปที่ส่วนอัลกอริทึม:

  1. สร้างอาร์เรย์เสริมขนาด 2n + 1 เพื่อเก็บจุดเริ่มต้นของค่าความแตกต่างที่เป็นไปได้ทั้งหมด (โปรดทราบว่าค่าความแตกต่างที่เป็นไปได้จะแตกต่างกันไปจาก -n ถึง n กล่าวคือมีค่าที่เป็นไปได้ทั้งหมด 2n + 1)
  2. เริ่มต้นจุดเริ่มต้นของความแตกต่างทั้งหมดเป็น -1
  3. เริ่มต้น maxLen เป็น 0 และผลรวมคำนำหน้าของทั้งสองอาร์เรย์เป็น 0 พรีซัม1 = 0, พรีซัม2 = 0
  4. สำรวจอาร์เรย์ทั้งสองจาก i = 0 ถึง n-1
    1. อัปเดตผลรวมคำนำหน้า: preSum1 + = arr1 [i], preSum2 + = arr2 [i]
    2. คำนวณความแตกต่างของผลรวมคำนำหน้าปัจจุบัน: curr_diff = preSum1 - preSum2
    3. ค้นหาดัชนีในอาร์เรย์ที่แตกต่างกัน: diffIndex = n + curr_diff // curr_diff สามารถเป็นลบและไปได้จนถึง -n
    4. If curr_diff คือ 0 ดังนั้น i + 1 คือ maxLen
    5. อื่น ๆ ถ้า เห็น curr_diff ในครั้งแรกนั่นคือจุดเริ่มต้นของค่าต่างปัจจุบันคือ -1 จากนั้นอัปเดตจุดเริ่มต้นเป็น i
    6. อื่น (ไม่เห็น curr_diff ในครั้งแรก) จากนั้นให้พิจารณา i เป็นจุดสิ้นสุดและค้นหาความยาวของช่วงผลรวมเดียวกันในปัจจุบัน หากความยาวมากกว่านี้ให้อัปเดต maxLen
  5. กลับ maxLen

การดำเนินงาน  

โปรแกรม C ++ สำหรับช่วงที่ยาวที่สุดที่มีผลรวมเท่ากันในสองอาร์เรย์ไบนารี II

#include<bits/stdc++.h> 
using namespace std; 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  int b[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  for(int i=0;i<n;i++)
  {
      cin>>b[i];
  }
  int maxLen = 0; 
  int ps1 = 0, ps2 = 0; 
  int temp[2*n+1]; 
  memset(temp, -1, sizeof(temp)); 
  for (int i=0; i<n; i++) 
  { 
    ps1 += a[i]; 
    ps2 += b[i]; 
    int curr_diff = ps1 - ps2; 
    int diff = n + curr_diff; 
    if (curr_diff == 0) 
      maxLen = i+1; 
    else if ( temp[diff] == -1) 
      temp[diff] = i; 
    else
    { 
      int len = i - temp[diff]; 
      if (len > maxLen) 
        maxLen = len; 
    } 
  } 
  cout<<maxLen<<endl; 
  return 0; 
} 

โปรแกรม Java สำหรับช่วงที่ยาวที่สุดที่มีผลรวมเท่ากันใน Binary Arrays II สองตัว

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        int a[]= new int[n];
        int b[]= new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sr.nextInt();
        }
        for(int i=0;i<n;i++)
        {
            b[i]=sr.nextInt();
        }
        int maxLen = 0; 
  int ps1 = 0, ps2 = 0; 
  int temp[] = new int [2*n+1]; 
  for(int i=0;i<2*n+1;i++)
        {
            temp[i]=-1;
        }
  for (int i=0; i<n; i++) 
  { 
    ps1 += a[i]; 
    ps2 += b[i]; 
    int curr_diff = ps1 - ps2; 
    int diff = n + curr_diff; 
    if (curr_diff == 0) 
      maxLen = i+1; 
    else if ( temp[diff] == -1) 
      temp[diff] = i; 
    else
    { 
      int len = i - temp[diff]; 
      if (len > maxLen) 
        maxLen = len; 
    } 
  } 
  System.out.println(maxLen); 
    }
}
10
1 0 0 0 1 1 0 1 1 0
0 0 1 0 1 1 0 1 0 0
9

การวิเคราะห์ความซับซ้อนสำหรับช่วงที่ยาวที่สุดที่มีผลรวมเท่ากันในสองอาร์เรย์ไบนารี II  

ความซับซ้อนของเวลา

O (n) โดยที่ n คือขนาดของอาร์เรย์ที่กำหนด“ a” หรือ“ b” ที่นี่เราไปที่อาร์เรย์และค้นหาความแตกต่างของผลรวมคำนำหน้าในตำแหน่ง

ดูสิ่งนี้ด้วย
เพิ่มผลรวมของความแตกต่างที่ต่อเนื่องกันสูงสุดในอาร์เรย์แบบวงกลม

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

O (n)  เนื่องจากเราประกาศอาร์เรย์ชั่วคราวซึ่งเราใช้ในการจัดเก็บดัชนี