ซับอาร์เรย์ขนาดใหญ่ที่สุดที่มีจำนวน 0 และ 1 เท่ากันใน C++

โจทย์

มาดูขั้นตอนในการทำโปรแกรม

• กำหนดอาร์เรย์
• ทำให้ศูนย์ทั้งหมดในอาร์เรย์กลายเป็น -1
• มีแมปว่างเพื่อเก็บดัชนีก่อนหน้า
• กำหนด sum เป็น 0, max length เป็น 0 และ ending index เป็น -1
• เขียนลูปที่วนรอบจนถึง n
  • บวกองค์ประกอบปัจจุบันเข้าไปใน sum
  • ถ้า sum เท่ากับ 0
    • อัปเดต max length ด้วย i + 1
    • และ ending index เป็น i
  • ถ้า sum มีอยู่ในแมป previous sums และ i - previousIndexes[sum] มากกว่า max length
    • อัปเดต max length และ ending index
  • มิฉะนั้น เพิ่ม sum เข้าไปในแมป previous indexes
• พิมพ์ดัชนีเริ่มต้น endingIndex - maxLength + 1 และ ending index endingIndex

ตัวอย่าง

มาดูโค้ดกัน

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

void findTheSubArray(int arr[], int n) { 
    unordered_map<int, int> previousIndexes; 
    int sum = 0, maxLength = 0, endingIndex = -1; 
    for (int i = 0; i < n; i++) { 
        arr[i] = arr[i] == 0 ? -1 : 1; 
    } 
    for (int i = 0; i < n; i++) { 
        sum += arr[i]; 
        if (sum == 0) { 
            maxLength = i + 1; 
            endingIndex = i; 
        } 
        if (previousIndexes.find(sum) != previousIndexes.end()) { 
            if (maxLength < i - previousIndexes[sum]) { 
                maxLength = i - previousIndexes[sum]; 
                endingIndex = i; 
            } 
        } else { 
            previousIndexes[sum] = i; 
        } 
    } 
    cout << endingIndex - maxLength + 1 << " " << endingIndex << endl; 
} 

int main() { 
    int arr[] = { 1, 1, 0, 0, 0, 1, 1, 1, 0 }; 
    findTheSubArray(arr, 9); 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

1 8

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้กล่าวถึงในส่วนความคิดเห็น