C++ में समान योग के साथ स्प्लिट ऐरे

मान लीजिए कि हमारे पास n पूर्णांकों के साथ एक सरणी है, हमें यह पता लगाना है कि क्या ट्रिपल (i, j, k) हैं जो इन शर्तों का पालन करते हैं -

0
उपसरणियों का योग (0, i-1), (i + 1, j-1), (j + 1, k-1) और (k + 1, n-1) समान होगा।

सबअरे (एल, आर) मूल सरणी का एक टुकड़ा है जो तत्व अनुक्रमित एल से शुरू होकर तत्व अनुक्रमित आर तक शुरू होता है।

इसलिए, अगर इनपुट [1,2,1,2,1,2,1] जैसा है, तो आउटपुट ट्रू होगा, जैसे कि 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]
इनिशियलाइज़ करने के लिए मैं :=1, जब i
- रकम [i]:=रकम [i] + (अंक [i] + रकम [i - 1])
इनिशियलाइज़ j :=3 के लिए, जब j - n, अपडेट करें (j को 1 से बढ़ाएँ), करें -
- एक सेट को परिभाषित करें
- इनिशियलाइज़ करने के लिए i :=1, जब i
  - sum1 :=sums[i - 1]
  - sum2 :=sums[j-1] - sums[i]
  - अगर sum1, sum2 के समान है, तो -
    - sum1 को s में डालें
- इनिशियलाइज़ k :=j + 2 के लिए, जब k
  - sum1 :=sums[k - 1] - sums[j]
  - sum2 :=sums[n - 1] - sums[k]
  - अगर sum1, sum2 के समान है और sum1 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}