সামান সামের সাবঅ্যারে দিয়ে অ্যারে স্প্লিট করা C++-এ

সমস্যা বিবরণ

একটি ইন্টিজার অ্যারে দেওয়া আছে। তিনটি ইন্ডেক্স i, j, k (০ < i, i+1 < j, j+1 < k < n-1) খুঁজে বের করতে হবে যাতে নিচের ৪টি সাবঅ্যারের সাম সমান হয়:

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

উদাহরণ

ইনপুট: [1,2,1,2,1,2,1]

i=1, j=3, k=5 দিয়ে ৪টি সাবঅ্যারে: [1], [1], [1], [1] — সবার সাম ১। আউটপুট: true।

অ্যালগরিদম: প্রিফিক্স সাম + সেট

1. প্রিফিক্স সাম অ্যারে sums বানান।
2. মাঝপথি ইন্ডেক্স j ফিক্স করুন (৩ থেকে n-3 পর্যন্ত)।
3. j-র বামপাশে সব সম্ভাব্য i দিয়ে চেক করুন: sum(0,i-1) == sum(i+1,j-1) হলে সেই সাম সেটে রাখুন।
4. j-র ডানপাশে সব সম্ভাব্য k দিয়ে চেক করুন: sum(j+1,k-1) == sum(k+1,n-1) এবং সেটে আছে কিনা।
5. পাওয়া গেলে true, না পেলে false।

C++ বাস্তবায়ন

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

class Solution {
public:
    bool splitArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n);
        sums[0] = nums[0];
        for (int i = 1; i < n; i++)
            sums[i] = sums[i-1] + nums[i];

        for (int j = 3; j < n; j++) {
            unordered_set<int> validSums;
            for (int i = 1; i < j - 1; i++) {
                int sum1 = sums[i-1];
                int sum2 = sums[j-1] - sums[i];
                if (sum1 == sum2) validSums.insert(sum1);
            }
            for (int k = j + 2; k < n - 1; k++) {
                int sum1 = sums[k-1] - sums[j];
                int sum2 = sums[n-1] - sums[k];
                if (sum1 == sum2 && validSums.count(sum1))
                    return true;
            }
        }
        return false;
    }
};

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

ইনপুট ও আউটপুট

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(n²) — j ও k-এর নেস্টেড লুপ।
• স্থান জটিলতা: O(n) — প্রিফিক্স সাম ও সেট।