题目

给定一个含有 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 <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5

进阶：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

做过很多滑窗题目后，滑窗是比较直接好想的办法，当和小于target时扩张右边界，当不小于target后，更新最小的长度，并尽可能收缩左边界直至和再次小于target。

题目的进阶内容比较奇怪，实现O(n)算法后，再实现一个nlogn的。子数组求和当然更常见的做法是前缀和，那么对于一个区间[i,j]，因为要求使preSum[j]-preSum[i]>=target成立的最大下标i，转变一下就是求最大的下标i使得preSum[i]<=preSum[j]-target。对于这道题，前缀和数组是严格递增的，因此可以使用二分求满足条件的下标i。

代码

前缀和+二分

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int n = nums.length;
  4.         int[] pre = new int[n + 1];
  5.         for (int i = 1; i <= n; i++) {
  6.             pre[i] = pre[i - 1] + nums[i - 1];
  7.         }
  8.         int ans = n + 1;
  9.         for (int i = 1; i <= n; i++) {
  10.             // 找最大的下标k使得pre[k]<=pre[i] - target
  11.             int k = bearch(pre, pre[i] - target);
  12.             // 如果返回-1，说明对于下标j，[0,j]中不存在一个下标i使得sum[i,j]>=target
  13.             if (k >= 0) {
  14.                 // k是区间左边界，i-1为区间右边界，因此区间长度为i-k
  15.                 ans = Math.min(ans, i - k);
  16.             }
  17.         }
  18.         return ans == n + 1 ? 0 : ans;
  19.     }
  21.     // 找出nums中最后一个不大于k的数，返回其下标，如果不存在，返回-1
  22.     private int bearch(int[] nums, int k) {
  23.         int l = 0;
  24.         int r = nums.length - 1;
  25.         while (l < r) {
  26.             int mid = l + (r - l + 1) / 2;
  27.             if (nums[mid] > k) {
  28.                 r = mid - 1;
  29.             } else {
  30.                 l = mid;
  31.             }
  32.         }
  33.         if (nums[l] <= k) {
  34.             return l;
  35.         }
  36.         return -1;
  37.     }
  38. }

滑窗

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int n = nums.length;
  4.         int left = 0;
  5.         int right = 0;
  6.         int sum = 0;
  7.         int ans = n + 1;
  8.         while (right < n) {
  9.             sum += nums[right];
  10.             while (sum >= target) {
  11.                 ans = Math.min(ans, right - left + 1);
  12.                 sum -= nums[left];
  13.                 left++;
  14.             }
  15.             right++;
  16.         }
  17.         return ans == n + 1 ? 0 : ans;
  18.     }
  19. }