给定一个长度为 n 的整数数组,和一个目标值 k ,请你找出这个整数数组中和大于等于 k 的最短子数组的长度。如果不存在和大于等于 k 的子数组则输出 -1。
数据范围:数组长度满足 , , 数组中的值满足
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param nums int整型一维数组 # @param k int整型 # @return int整型 # class Solution: def shortestSubarray(self , nums: List[int], k: int) -> int: # write code here # 解题思路: # 数组中的值满足 1 <= num <= 100000,都大于0,不需要考虑负数 # 使用双指针,左右指针都从0开始,sum初值为nums[0] # 如果sum >= k,则左指针右移,sum减掉最左边的数字,寻找更短的数组 # 否则,右指针右移,sum加上右边的数字,以满足 sum>=k # 如果右指针超界,说明没有继续搜索的必要,直接跳出,提高效率 # 如果左指针超过右指针,说明找到单独一个数字大于k,结果为1,不必再判断其余 # 最后返回结果 sum = nums[0] left = 0 right = 0 size = len(nums) result = size + 1 while left < size and left <= right: if sum >= k: result = min(result,right-left+1) sum -= nums[left] left += 1 else: right += 1 if right >= size: break sum += nums[right] result = result if result <= size else -1 return result