Ang Li

Leetcode题解 209: Minimum Size Subarray Sum

2020/04/02

题目内容

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

题目样例

Example:

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation: the subarray [4,3] has the minimal length under the problem constraint.

题目分析

本题的核心在于由于要求SubArray,所以不能用排序

暴力做法是列出所有的可能的 SubString, 共有 n * (n - 1) / 2 个， 然后看哪个是符合要求的子数组。时间复杂度是 O(n * n)

暴力方法会因为时间复杂度过高而很难通过。为了减少时间复杂度，有一个可以参照的思路是Sliding Window （移动窗）。

举例说明

假设数组为：s = 7 nums = [2, 3, 1, 2, 4, 3]

先放两个指针 i, j = 0, 1

下一步我们计算窗内数字的总和

如果窗内数字的总和小于s 则右指针右移 扩大窗口大小 使窗内数字总和sum大于等于目标s 反之如果窗内数字的总和大于等于s 我们则将左指针右移缩小窗口 以测试更短长度下的窗内总和满不满足条件

Nums[i] + Nums[j] < 7 右指针右移 扩充窗口大小

I到j之间的数相加 < 7 右指针右移 扩充窗口大小

i到j之间的数相加2 + 3 + 1 + 2 > 7 右指针右移 扩充窗口大小 记录窗口大小为最短长度 res = j - i + 1 = 4

左指针右移 缩小窗口 尝试检测缩小窗口后是否满足条件

3 + 1 + 2 < 7，右指针右移扩大窗口 扩大后3 + 1 + 2 + 4 > 7 长度4等于res, 结果res不变化

左指针右移 缩小窗口 尝试检测缩小窗口后是否满足条件 1 + 2 + 4 = 7 满足条件。 长度3小于4， 将最短长度更新为3

左指针右移 缩小窗口 尝试检测缩小窗口后是否满足条件， 2 + 4 < 7，右指针右移扩大窗口

1 + 2 + 4 = 7，满足条件。 长度3等于最短长度3，无需更新

左指针右移 缩小窗口 尝试检测缩小窗口后是否满足条件 4 + 3 == 7，条件满足。长度2小于3， 将最短长度更新为2

最短长度为res = 2

代码实现

Python

def findSubArray(l, target):
	
	if  len(l) < 1:
		return  0
		
	if  len(l) == 1:
		if l[0] >= target:
			return  1
		else:
			return  0
			
	if l[0] >= target:
		return  1
		
	i, j = 0, 1
	res = len(l) + 1
	sum = l[i]
	while j < len(l):
		sum += l[j]
		while  sum >= target and i <= j:
			res = min(j - i + 1, res)
			if i < j:
				sum -= l[i]
				i += 1
			else:
				break
		j += 1
		
	if res < len(l) + 1:
		return res
    else:
	    return 0

注意事项

  1. 由于使用双指针算法 本题应考虑当数组长度为0或1时的情况
  2. 应考虑左指针i为零时是否满足大于目标s 的情况 因为同向双指针的起始点分别为0和 1,所以会把nums[0] > s的状况忽略
  3. 本题的关键在于窗内大小满足条件时，左指针右移，尝试缩小窗口，将答案确保为最小。如果不满足条件时，右指针右移继续前进

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

相似题目

Leetcode 76: Minimum Window Substring

Leetcode 325: Maximum Size Subarray Sum Equals k

Leetcode 718: Maximum Length of Repeated Subarray

Post Directory