本文共 538 字,大约阅读时间需要 1 分钟。
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]输出: 2解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
思路:设置左右滑动指针,一开始两个指针都处于数组左边,不断右移右指针,直到子序列和大于等于s,接下来我们在此基础上尽可能缩短序列的长度,不断向右滑动左指针,更新连续子数组长度最小值。
class Solution {public: int minSubArrayLen(int s, vector & nums) { int i=0, j=0, re=INT_MAX, sum=0; while(j=s){ re=min(re, j-i); sum-=nums[i++]; } } return re
转载地址:http://iqabi.baihongyu.com/