題目描述

題目鏈接：【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