Mảng con ngắn nhất có tổng ít nhất K trong C++

Cho mảng A, tìm độ dài mảng con liên tiếp ngắn nhất có tổng ≥ K. Không có thì -1.

Ví dụ: [5,3,-2,2,1], K=6 → 2 (mảng con [5,3]).

Giải thuật

1. Tính tiền tố: A[i] += A[i-1].
2. Dùng deque lưu chỉ số tăng dần theo giá trị tiền tố.
3. Duyệt i:
   • Nếu A[i] ≥ K: ans = min(ans, i+1).
   • Trong khi deque không rỗng và A[i] - A[deque.front()] ≥ K: ans = min(ans, i - deque.front()), pop_front.
   • Trong khi deque không rỗng và A[i] ≤ A[deque.back()]: pop_back.
   • Push i vào deque.
4. Trả về ans hoặc -1.

Ví dụ mã C++

#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;
        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;
    }
};
int main(){
    Solution ob;
    vector<int> v = {5,3,-2,2,1};
    cout << (ob.shortestSubarray(v, 6));
}

Đầu vào

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

Đầu ra

2