Subarray ที่สั้นที่สุดพร้อม Sum อย่างน้อย K ใน C++

สมมติว่าเรามีอาร์เรย์ A เราต้องหาความยาวของอาร์เรย์ย่อยที่สั้นที่สุด ไม่ว่าง และต่อเนื่องกันของ A ซึ่งมีผลรวมอย่างน้อย K หากไม่มีอาร์เรย์ย่อยดังกล่าว ให้คืนค่า -1

ดังนั้น หากอินพุตเป็น [5,3,-2,2,1] และ k =6 ผลลัพธ์จะเป็น 2 ดังที่เราเห็น (5+3)>=6

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ A

• ตอบ :=n + 1, j :=0, sum :=0

• กำหนดหนึ่ง deque dq

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า i> 0 แล้ว −

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

  • ถ้า A[i]>=K แล้ว −

    • ans :=ขั้นต่ำของ ans และ i + 1

  • ในขณะที่ (ไม่ใช่ dq ว่างเปล่าและของ A[i] - องค์ประกอบแรก A[dq]>=K) ทำ -

    • ans :=ขั้นต่ำของ ans และองค์ประกอบแรกของ i - dq

    • ลบองค์ประกอบด้านหน้าออกจาก dq

  • ในขณะที่ (ไม่ใช่ dq ว่างเปล่าและ A[i] <=องค์ประกอบสุดท้ายของ A[dq] ทำ -

    • ลบองค์ประกอบสุดท้ายออกจาก dq

  • ใส่ i ต่อท้าย dq

• return (ถ้า ans เหมือนกับ n + 1 แล้ว -1 มิฉะนั้น ans)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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