C++ এ সমান সমষ্টি সহ অ্যারে বিভক্ত করুন

ধরুন আমাদের কাছে n পূর্ণসংখ্যা সহ একটি অ্যারে আছে, আমাদের খুঁজে বের করতে হবে সেখানে ট্রিপলেট (i, j, k) আছে কিনা যা এই শর্তগুলি অনুসরণ করে −

0
(0, i - 1), (i + 1, j - 1), (j + 1, k - 1) এবং (k + 1, n - 1) এর যোগফল একই হবে৷

সাব্যারে (L, R) হল মূল অ্যারের একটি স্লাইস যা L থেকে শুরু করে সূচীকৃত L থেকে এলিমেন্ট ইন্ডেক্স করা R পর্যন্ত হয়।

সুতরাং, যদি ইনপুটটি [1,2,1,2,1,2,1] এর মত হয়, তাহলে আউটপুটটি True হবে, যেমন i =1, j =3, k =5।

sum(0, i - 1) = 1 sum(0, 0) = 1
sum(i + 1, j - 1) = 1 sum(2, 2) = 1
sum(j + 1, k - 1) = 1 sum(4, 4) = 1
sum(k + 1, n - 1) = 1 sum(6, 6) = 1

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

n :=সংখ্যার আকার
n
আকারের একটি অ্যারের যোগফল সংজ্ঞায়িত করুন
যোগফল[0] :=সংখ্যা[0]
আরম্ভ করার জন্য i :=1, যখন i
- যোগফল[i] :=যোগফল[i] + (সংখ্যা[i] + যোগফল[i - 1])
j শুরু করার জন্য :=3, যখন j − n, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
- একটি সেট s
  সংজ্ঞায়িত করুন
- আরম্ভ করার জন্য i :=1, যখন i
  - যোগফল1 :=যোগফল[i - 1]
  - যোগফল2 :=যোগফল[j - 1] - যোগফল[i]
  - যদি যোগফল 2 এর সমান হয়, তাহলে −
    - s
      এর মধ্যে যোগফল 1 সন্নিবেশ করান
- আরম্ভ করার জন্য k :=j + 2, যখন k
  - যোগফল1 :=যোগফল[k - 1] - যোগফল[j]
  - যোগফল2 :=যোগফল[n - 1] - যোগফল[k]
  - যদি যোগফল 2 এর মত হয় এবং যোগফল 1 s তে থাকে, তাহলে −
    - প্রত্যাবর্তন সত্য
ফেরত মিথ্যা

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#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] += (nums[i] + sums[i - 1]);
      }
      for (int j = 3; j < n; j++) {
         set<int> s;
         for (int i = 1; i < j - 1; i++) {
            int sum1 = sums[i - 1];
            int sum2 = sums[j - 1] - sums[i];
            if (sum1 == sum2)
               s.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 && s.count(sum1))
               return true;
            }
         }
         return false;
      }
};
main(){
   Solution ob;
   vector<int> v = {1,2,1,2,1,2,1};
   cout << (ob.splitArray(v));
}

ইনপুট

{1,2,1,2,1,2,1}