题目描述

题目链接：【LeetCode】209. 长度最小的子数组（前缀和 + 二分）

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

找出该数组中满足其总和大于等于 target 的长度最小的子数组 $[{\text{nums}}_l,{\text{nums}}_{l+1},\dots ,{\text{nums}}_{r-1},{\text{nums}}_r]$ 返回其长度。如果不存在符合条件的子数组，返回 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 <= $10^9$
1 <= nums.length <= $10^5$
1 <= nums[i] <= $10^4$

进阶：

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

前缀和

class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length, res = Integer.MAX_VALUE;int[] sum = new int[n];for (int i = 0; i < n; i++) {sum[i] = (i == 0) ? nums[0] : sum[i - 1] + nums[i];if (nums[i] >= target) {return 1;}if (sum[i] >= target) {res = Math.min(res, i + 1);}}for (int i = 0; i < n; i++) {for (int j = i; j < n && j - i <= res; j++) {if (sum[j] - sum[i] >= target) {res = Math.min(res, j - i);break;}}}return res == Integer.MAX_VALUE ? 0 : res;}}

超出时间限制 18 / 21 个通过的测试用例

二分优化

class Solution {public int minSubArrayLen(int target, int[] nums) {int res = Integer.MAX_VALUE, n = nums.length;// 前缀和int[] sums = new int[n];for (int i = 0; i < n; i++) {sums[i] = (i == 0) ? nums[0] : sums[i - 1] + nums[i];if (nums[i] >= target) {return 1;}if (sums[i] >= target) {res = Math.min(res, i + 1);}}// 二分for (int i = 0; i < n; i++) {int index = search(sums, sums[i] + target);res = (index == -1 || index == sums.length) ? res : Math.min(res, index - i);}return res == Integer.MAX_VALUE ? 0 : res;}public int search(int[] sums, int sum) {int l = -1, r = sums.length;while (l + 1 != r) {int m = (l + r) / 2;if (sums[m] < sum) {l = m;} else {r = m;}}return r;}}

前缀和总结

两种前缀和数组定义：

第一种定义：

S[0] = 0, S[i] = A[0] + A[1] + … + A[i-1] (i>=1)
区间和计算： Sum(L, R) = S[R+1] - S[L] (求 A[L] 到 A[R] 的和)

for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + nums[i];
}

sum[left, right] = prefix[right+1] - prefix[left]

第二种定义：

S[0] = A[0], S[i] = A[0] + … + A[i] (i>=0)
注意：在第二种定义下，当L=0时，我们需要单独处理，以避免S[L-1]出现负数下标。

for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + nums[i];
}

sum[left, right] = prefix[right] - (left>0 ? prefix[left-1] : 0)

二分总结

二分模板：

l = -1, r = N
while l + 1 ≠ r:m = ⌊(l + r)/2⌋if IsBlue(m):l = melse:r = m
return l or r

查找目标	IsBlue条件	返回的值
第一个 ≥target 的元素	<target	r
最后一个 <target 的元素	<target	l
第一个 >target 的元素	≤target	r
最后一个 ≤target 的元素	≤target	l