长度最小的子数组题解

题目

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

  • 1 <= target <= 109

  • 1 <= nums.length <= 105

  • 1 <= nums[i] <= 105

题解

首先这里可以用暴力想到,直接遍历每个子数组,求和,然后取每趟最小的那个序列。这里有一个小tips:在每个求和的子序列中,一旦找到第一个符合要求的长度,那么这轮最小长度必然是该长度,这时直接跳出循环,进行下一轮循环就可以了,代码也很简单。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        length = len(nums)
		# 这里的minLen初始值给它设置为无穷大
        minLen = float('inf')
		for i in range(length):
			sums = 0
			for j in range(i,length):
				sums += nums[j]
				if sums >= target:
					minLen = min(minLen,i-j +1)
					break
        return 0 if minLen == float('inf') else minLen

这种写法双循环,时间复杂度O(n^2),空间复杂度O(1)

为了优化这种方法,考虑是否可以一轮遍历就完成最小值的筛选?答案是可以的,使用滑动窗口策略可以达到这个目的。

这里我的想法是:既然要在一次循环内完成最小子数组长度的筛选,不仅需要一个指针在前面“拉”,还需要在每次计算完sum值之后,在后面“推”,把区间“挤”到其可能的最小值,图来自代码随想录:

根据这个思路,代码如下所示:

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        length = len(nums)
        minLen, sums, i = float('inf'), 0, 0
        for j in range(length):
            sums += nums[j]
            while target <= sums:
                minLen = min(minLen, j - i + 1)
                sums -= nums[i]
                i += 1
        return 0 if minLen == float('inf') else minLen

在每次循环计算过后,i指针都会往前“挤”,直到挤到小于targe的大小,然后j指针再向前“寻找机会”。

该算法一次遍历,时间复杂度为O(n),空间复杂度为常量。

dark
sans