题目

给定一个含有 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] <= 104

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题

暴力解法

第一反应是暴力解法，遍历所有的子数组，计算每个子数组的和，如果大于等于 target，就更新最小长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

func minSubArrayLen(target int, nums []int) int {
	minLen := len(nums) + 1

	for start := 0; start < len(nums); start++ {
		for sum, end := 0, start; end < len(nums); end++ {
			if sum += nums[end]; target <= sum {
				minLen = min(minLen, end-start+1)
				break
			}
		}
	}

	if minLen == len(nums)+1 {
		minLen = 0
	}

	return minLen
}

时间复杂度：O(n^2)
空间复杂度：O(1)

滑动窗口

暴力解法的时间复杂度是 O(n^2)，看了题解，发现可以使用滑动窗口来优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func minSubArrayLen(target int, nums []int) int {
	minLen := len(nums) + 1

	for start, end, sum := 0, 0, 0; start < len(nums) && end < len(nums); {
		for sum < target && end < len(nums) {
			sum += nums[end]
			end++
		}

		for sum >= target && start < len(nums) {
			minLen = min(minLen, end-start)
			sum -= nums[start]
			start++
		}
	}

	if minLen == len(nums)+1 {
		minLen = 0
	}

	return minLen
}

这个解法的时间复杂度是 O(n)，空间复杂度是 O(1)。

主要思路是使用两个指针，start 和 end，分别表示子数组的起始和结束位置。sum 用来记录当前子数组的和。然后每次移动 end 指针扩大窗口，直到 sum 大于等于 target，再移动 start 指针缩小窗口，直到 sum 小于 target。在这个过程中，不断更新最小长度。

第一次遇到数组中使用滑动窗口的题，花了很多时间，这个题值得记录下来。