Split Array with Equal Sum – แบ่งอาร์เรย์ 4 ส่วนผลรวมเท่ากันใน C++

ปัญหา: Split Array with Equal Sum

กำหนดอาร์เรย์ nums หา triplet (i, j, k) ที่:
0 < i, i+1 < j, j+1 < k < n-1
ทำให้ 4 ส่วนต่อไปนี้มีผลรวมเท่ากัน:

• sum(0, i-1)
• sum(i+1, j-1)
• sum(j+1, k-1)
• sum(k+1, n-1)

หมายเหตุ: ตำแหน่ง i, j, k เอง ไม่รวม ในส่วนใดส่วนหนึ่ง (เป็นตัวแบ่ง)

ตัวอย่าง

nums = [1,2,1,2,1,2,1], n = 7
i=1, j=3, k=5:
sum(0,0)=1, sum(2,2)=1, sum(4,4)=1, sum(6,6)=1 → true

แนวทางแก้ปัญหา: Prefix Sum + Hash Set

ขั้นตอน

1. คำนวณ prefix[i] = sum(0..i)
2. วน j (ตัวแบ่งกลาง) จาก 3 ถึง n-3:
   • สร้าง Set valid_sums สำหรับ left side
   • วน i จาก 1 ถึง j-2:
     • sum1 = prefix[i-1]
     • sum2 = prefix[j-1] - prefix[i]
     • ถ้า sum1 == sum2 → ใส่ sum1 ลง Set
3. สำหรับ j เดียวกัน วน k จาก j+2 ถึง n-2:
   • sum3 = prefix[k-1] - prefix[j]
   • sum4 = prefix[n-1] - prefix[k]
   • ถ้า sum3 == sum4 และ sum3 อยู่ใน Set → true

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

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

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        if (n < 7) return false; // ต้องมีอย่างน้อย 7 ตัว (4 ส่วน + 3 divider)

        vector<int> prefix(n);
        prefix[0] = nums[0];
        for (int i = 1; i < n; i++)
            prefix[i] = prefix[i-1] + nums[i];

        for (int j = 3; j < n - 2; j++) {
            unordered_set<int> leftSums;

            // Find valid left splits (i)
            for (int i = 1; i < j - 1; i++) {
                int sum1 = prefix[i-1];
                int sum2 = prefix[j-1] - prefix[i];
                if (sum1 == sum2)
                    leftSums.insert(sum1);
            }

            // Check right splits (k)
            for (int k = j + 2; k < n - 1; k++) {
                int sum3 = prefix[k-1] - prefix[j];
                int sum4 = prefix[n-1] - prefix[k];
                if (sum3 == sum4 && leftSums.count(sum3))
                    return true;
            }
        }
        return false;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,1,2,1,2,1};
    cout << (ob.splitArray(v) ? "true" : "false"); // true
    return 0;
}

ความซับซ้อน

• เวลา: O(n²) – ลูป j (n) × ลูป i/k (n)
• พื้นที่: O(n) – prefix array + set

ข้อสังเกต

• LeetCode 548
• Prefix sum ทำให้ query sum(L,R) = O(1)
• Set ใช้ตรวจสอบว่ามี left sum ที่ตรงกับ right sum หรือไม่
• Edge case: n < 7 → false ทันที
• โค้ดต้นฉบับมี typo: sums[i] += (nums[i] + sums[i - 1]) ควรเป็น sums[i] = sums[i-1] + nums[i]