मान लीजिए हमारे पास n पूर्णांकों वाली एक सरणी है, हमें यह ढूंढना है कि क्या ट्रिपलेट्स (i, j, k) हैं जो इन शर्तों का पालन करते हैं:
- 0 < i, i + 1 < j, j + 1 < k < n - 1
- उपसरणियों (0, i - 1), (i + 1, j - 1), (j + 1, k - 1) और (k + 1, n - 1) का योग समान होगा।
उपसरणी (L, R) मूल सरणी का एक टुकड़ा है जो इंडेक्स 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 = nums का आकार।
- प्रीफिक्स योग सरणी sums बनाएं।
- j = 3 से n-1 तक लूप करें।
- एक सेट s परिभाषित करें।
- i = 1 से j-2 तक: sum1 = sums[i-1], sum2 = sums[j-1] - sums[i]। यदि sum1 == sum2, तो s में sum1 डालें।
- k = j+2 से n-2 तक: sum1 = sums[k-1] - sums[j], sum2 = sums[n-1] - sums[k]। यदि sum1 == sum2 और sum1 s में है, तो true लौटाएं।
- false लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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}
आउटपुट
1
