Độ dài mảng con nhỏ nhất với tổng lớn hơn hoặc bằng S trong C++

Cho mảng n phần tử và số nguyên dương s. Tìm độ dài nhỏ nhất của mảng con liên tiếp có tổng ≥ s. Nếu không tồn tại trả về 0. Ví dụ: [2,3,1,2,4,3], s=7 → 2 (mảng con [4,3]).

Giải thuật

• ans := 0, n := kích thước mảng, j := 0, sum := 0.
• Với i từ 0 đến n-1:
  • sum += A[i].
  • Khi sum - A[j] ≥ K và j ≤ i: sum -= A[j], j++.
  • Nếu sum ≥ K: nếu ans == 0 hoặc ans > i-j+1 thì ans = i-j+1.
• Trả về ans.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSubArrayLen(int K, vector<int>& A) {
        int ans = 0, n = A.size(), j = 0, sum = 0;
        for (int i = 0; i < n; i++) {
            sum += A[i];
            while (sum - A[j] >= K && j <= i) {
                sum -= A[j];
                j++;
            }
            if (sum >= K) {
                if (ans == 0 || ans > (i - j + 1)) ans = (i - j + 1);
            }
        }
        return ans;
    }
};

Đầu vào

7 [2,3,1,2,4,3]

Đầu ra

2