C++ 中的最小大小子数组和

假设我们有一个包含 n 个元素和正整数 s 的数组。我们需要找到一个连续子串的最小长度，其和大于或等于 s。如果没有，则返回 0。因此，如果数组类似于 [2,3,1,2,3,4] 且和为 7，则输出将为 2。这是此案例中具有最小长度的子字符串 [4,3]。

为解决此问题，我们将遵循以下步骤：

  • ans := 0，n := 数组 A 的大小，j := 0 和 sum := 0

  • 对于从 0 到 n-1 的 i

    • sum := sum + A[i]

    • 当 sum – A[i] >= k 且 j <= 1 时

      • sum := sum – A[j]

      • 将 j 增加 1

    • 如果 sum >= k，则

      • 如果 ans = 0 或 ans > (i – j + 1)，则 ans := (i – j + 1)

  • 返回 ans

让我们了解一下以下实现以便更好地理解：

示例

 现场演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minSubArrayLen(int K, vector<int>& A) {
      int ans = 0;
      int n = A.size();
      int j = 0;
      int 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;
   }
};
main(){
   vector<int> v = {2,3,1,2,4,3};
   Solution ob;
   cout << ((ob.minSubArrayLen(7,v)));
}

输入

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

输出

2

更新于：2020 年 4 月 30 日

1K+ 查看

开启您的 职业生涯

完成课程以获得认证

立即开始
广告