406. 和大于S的最小子数组
2021-05-05 16:27
标签：rop 测试 case bpa lis pdo red top 初始 给定一个由 样例 1: 样例 2: 如果你已经完成了O(nlogn)时间复杂度的编程，请再试试 O(n)时间复杂度。 同向型双指针 406. 和大于S的最小子数组 标签：rop 测试 case bpa lis pdo red top 初始 原文地址：https://www.cnblogs.com/yunxintryyoubest/p/13192505.html406. 和大于S的最小子数组
n 个正整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。样例
输入: [2,3,1,2,4,3], s = 7
输出: 2
解释: 子数组 [4,3] 是该条件下的最小长度子数组。
输入: [1, 2, 3, 4, 5], s = 100
输出: -1
挑战
class Solution:
"""
@param nums: an array of integers
@param s: An integer
@return: an integer representing the minimum size of subarray
"""
"""
大致思路：
1.双指针，同时移动，如果sum大于s，则i 向右边移动，如果sum小于s，则j += 1,一直到sum大于s（一直循环到长度l为止，不符合条件，则不作比较)
2.最后判断min_nums,返回min_nums
"""
def minimumSize(self, nums, s):
if sum(nums) return -1
#初始化
l = len(nums)
min_nums,sums = l + 1, 0
#第二个指针，一直走到sum >= s,则跳出循环
j = 0
#同向型双指针
for i in range(l):
#如果是小于s的话，则一直在里面循环
while j s:
sums += nums[j]
j += 1
if sums >= s:
min_nums = min(min_nums, j - i)
#上面已经满足条件，第一个指针开始缩小区间，开始向右边移动
sums -= nums[i]
return min_nums