首页 > 试题广场 >

长度最小的连续子数组

[编程题]长度最小的连续子数组
  • 热度指数:3458 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个数组 nums 和一个正整数 target , 找出满足和大于等于 target 的长度最短的连续子数组并返回其长度,如果不存在这种子数组则返回 0。

数据范围:数组长度满足 ,数组中的元素满足
示例1

输入

[1,2,4,4,1,1,1],9

输出

3
示例2

输入

[1,4,4,4,1,1,1],3

输出

1
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def minSubarray(self , nums: List[int], target: int) -> int:
        # write code here
        left = 0
        right = 0
        sum = 0

        min_len = len(nums)
        found = False

        # 采用左闭右开的方式
        while left < len(nums):
            # sum不够则伸长
            if sum < target:
                if right < len(nums):
                    sum += nums[right]
                    right += 1
                else:
                    break
            # 查看值并开始缩减长度
            else:
                found = True

                min_len = min(min_len, right - left)
                sum -= nums[left]
                left += 1
        
        if found:
            return min_len
        else:
            return 0

编辑于 2024-04-24 22:02:25 回复(0)
class Solution:
    def minSubarray (self, nums, s: int) -> int:
        l = len(nums)
        left = 0
        right = 0
        min_len =l
        cur_sum = 0  # 当前的累加值

        while right < l:
            cur_sum += nums[right]

            while cur_sum >= s:  # 当前累加值大于目标值
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1

            right += 1
           
        return min_len
编辑于 2024-02-03 23:59:14 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def minSubarray(self , nums: List[int], targetint) -> int:
        # write code here
        n = len(nums)
        res = n
        slow = 0
        fast = 0
        sums = 0
        if not nums:
            return 0   #排除特殊情况
        for i in range(n):
            sums += nums[i]
        if sums < target:
            return 0   #排除特殊情况
        sums = 0
        while fast < n:
            sums += nums[fast]
            fast += 1
            while slow < fast and sums >= target:
                res = min(res,fast - slow)
                sums -= nums[slow]
                slow += 1
        return res
发表于 2022-09-16 09:32:24 回复(0)

问题信息

难度:
3条回答 1883浏览

热门推荐

通过挑战的用户

查看代码