本文共 1504 字，大约阅读时间需要 5 分钟。
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶：
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
解题思路1： 双指针法O(n)，设置left和right两个指针，然后统计nums[left]到nums[right]的大小，当大小大于s时，因为输入全为正数，我们可以考虑不断丢弃left位的值来找出满足大于s的最短子数组长度right-left+1。
int minSubArrayLen(int s, vector & nums) { int left=0,right=0; int sum = 0; int minLen = INT_MAX; //长度为0 if(nums.size() == 0) return 0; while(right = s){ minLen = min(minLen, right-left+1); sum -= nums[left]; left++; } right++; } return minLen==INT_MAX? 0:minLen; } 解题思路2：前缀加二分查找方法O(nlogn), 这个题最暴力的解法就是两重for循环，第一重即遍历数组得到起始位i，第二重则从i开始遍历，找到满足>=s的解的长度。第一重循环是一定需要的，但是第二重循环可以做优化。我们可以事先开辟一个数组sums去得到记录当前位置i的[0: i-1]个元素的和。因为输入都为正数，那么sums一定是个递增的数组。接着当我们遍历数组nums时，我们只需要在sum中找到满足大于等于nums[i] + s的sums[j], 此时j-i+1就是以元素i为起点的最短的子数组长度
//寻找s中大于等于t的元素下界下标int lowerBound(vector &s, int t){ int left=0, right=s.size()-1; while(left = t ? left:-1;}int minSubArrayLen(int s, vector & nums) { if(nums.size() == 0) return 0; //获取前缀和 从1开始 sums[0]代表前0个元素之和为0 vector sums(nums.size()+1, 0); for(int i=1;i 转载地址：https://blog.csdn.net/weixin_31990755/article/details/112378936 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
