सी ++ में कम से कम के योग के साथ सबसे छोटा सबरे

मान लीजिए कि हमारे पास एक सरणी ए है। हमें ए की सबसे छोटी, गैर-रिक्त, सन्निहित उप-सरणी की लंबाई का पता लगाना है, जिसका योग कम से कम के है। यदि ऐसा कोई उप-सरणी नहीं है, तो वापसी -1।

इसलिए, यदि इनपुट [5,3,-2,2,1] और k =6 जैसा है, तो आउटपुट 2 होगा, जैसा कि हम देख सकते हैं (5+3)>=6

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=A का आकार

• उत्तर:=एन + 1, जे:=0, योग:=0

• एक डेक डीक्यू परिभाषित करें

• इनिशियलाइज़ i:=0 के लिए, जब i

  • अगर मैं> 0, तो -

    • ए[i] :=ए[i] + ए[i - 1]

  • यदि A[i]>=K, तो −

    • उत्तर:=न्यूनतम उत्तर और i + 1

  • जबकि (dq खाली नहीं है और A[i] - पहला तत्व A[dq]>=K) है, तो −

    करें

    • उत्तर:=न्यूनतम उत्तर और i - dq का पहला तत्व

    • dq से सामने का तत्व हटाएं

  • जबकि (dq खाली नहीं है और A[i] <=A[dq] का अंतिम तत्व, करते हैं -

    • dq से अंतिम तत्व हटाएं

  • dq के अंत में i डालें

• वापसी (यदि उत्तर n + 1 के समान है, तो -1, अन्यथा उत्तर)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int shortestSubarray(vector<int> &A, int K) {
      int n = A.size();
      int ans = n + 1;
      int j = 0;
      int sum = 0;
      deque<int> dq;
      for (int i = 0; i < n; i++) {
         if (i > 0)
         A[i] += A[i - 1];
         if (A[i] >= K) {
            ans = min(ans, i + 1);
         }
         while (!dq.empty() && A[i] - A[dq.front()] >= K) {
            ans = min(ans, i - dq.front());
            dq.pop_front();
         }
         while (!dq.empty() && A[i] <= A[dq.back()])
         dq.pop_back();
         dq.push_back(i);
      }
      return ans == n + 1 ? -1 : ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {5,3,-2,2,1};
   cout << (ob.shortestSubarray(v, 6));
}

इनपुट

{5,3,-2,2,1}, 6

आउटपुट

2