深圳建筑图片大全高清_外包小程序开发技巧_百度推广电话客服24小时_北京知名seo公司精准互联

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解法

class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int n = nums.size();if (n == 0) {return 0;}int ans = INT_MAX;vector<int> sums(n + 1, 0); // 为了方便计算，令 size = n + 1 // sums[0] = 0 意味着前 0 个元素的前缀和为 0// sums[1] = A[0] 前 1 个元素的前缀和为 A[0]// 以此类推for (int i = 1; i <= n; i++) {sums[i] = sums[i - 1] + nums[i - 1];}for (int i = 1; i <= n; i++) {int target = s + sums[i - 1];auto bound = lower_bound(sums.begin(), sums.end(), target);if (bound != sums.end()) {ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1)));}}return ans == INT_MAX ? 0 : ans;}
};

二分查找查的是前缀和数组