แบ่งเป็น 3 ส่วนเท่ากันใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A ของ 0 และ 1 แบ่งเป็น 3 ส่วนไม่ว่าง ที่แทนค่า binary เท่ากัน คืน [i,j] ที่ i+1

ตัวอย่าง

A = [0,1,0,1,1] → Output: [0,4]

ข้อสังเกตสำคัญ

• จำนวน 1 ทั้งหมดต้องหาร 3 ลงตัว
• ส่วนท้าย (third part) กำหนด pattern ของ 1 และ 0 นำหน้า (leading zeros)
• ส่วนแรกและสองต้อง match pattern เดียวกันหลังข้าม leading zeros

แนวทางแก้ปัญหา

1. นับจำนวน 1 ทั้งหมด (num) ถ้า num%3≠0 → [-1,-1]
2. ถ้า num==0 → คืน [0,2] (แบ่งได้ทุกอย่าง)
3. req = num/3 (จำนวน 1 ต่อส่วน)
4. หาตำแหน่งเริ่มต้นของส่วนที่ 3 (idx) โดยนับ 1 จากขวา req ตัว
5. ฟังก์ชัน getIdx(left, right): หาจุดสิ้นสุดของส่วน
   • ข้าม leading zeros ด้วย while(left
   • เปรียบเทียบ a[left..] กับ a[right..] ต้องเหมือนกันทุกตัว
   • คืน left-1 (ตำแหน่งสุดท้ายของส่วน)
6. firstEnd = getIdx(0, idx)
7. secondEnd = getIdx(firstEnd+1, idx)
8. คืน [firstEnd, secondEnd+1]

ตัวอย่างโค้ด C++

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

class Solution {
    int getIdx(vector<int>& a, int left, int right) {
        while(left < right && a[left] == 0) left++;
        while(right < a.size()) {
            if(a[left] != a[right]) return -1;
            left++; right++;
        }
        return left - 1;
    }
    
public:
    vector<int> threeEqualParts(vector<int>& A) {
        vector<int> ret = {-1, -1};
        int num = 0, n = A.size();
        for(int x : A) num += x;
        if(num % 3 != 0) return ret;
        if(num == 0) return {0, 2};
        
        int req = num / 3;
        int idx = n - 1;
        for(int temp=0; idx>=0 && temp