Leetcode刷题209. 长度最小的子数组

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

进阶：

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

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

感谢windliang的详细通俗的思路分析，多解法，感谢数据结构和算法的Java 的 5 种解法，最好的击败了 99.85% 的用户

class Solution {public int minSubArrayLen(int target, int[] nums) {
//		return minSubArrayLenI(target, nums);
//		return minSubArrayLenII(target, nums);return minSubArrayLenIII(target, nums);}//方法三：前缀和+二分查找，时间复杂度O(NlogN)，空间复杂度O(N)//由于数组元素都是正整数，定义新的数组sum[i]，表示从0到i的累加和，这样就得到一个有序数组//通过sum数组，如果要求i到j的所有子数组的和，就等于前j个数字的和减去前i-1个数字的和，即sum[j]-sum[i-1]//与方法一类似，利用sum数组分别求出从0,1,2....个数字开始，总和大于等于target时的长度//比如求从第i个数字开始，总和大于等于target时的长度，sum[j]-sum[i-1] >= target -> sum[j] >= target + sum[i-1]private int minSubArrayLenIII(int target, int[] nums) {if (nums == null || nums.length == 0) {return 0;}int len = nums.length;int min = Integer.MAX_VALUE;int[] sum = new int[len + 1];for (int i = 1; i <= len; i++) {sum[i] = sum[i - 1] + nums[i - 1];}for (int i = 1; i <= len; i++) {int s = target + sum[i - 1];int index = findLeftBound(sum, s);if (index != -1) {min = Math.min(min, index - i + 1);}}return min == Integer.MAX_VALUE ? 0 : min;}private int findLeftBound(int[] nums, int target) {int len = nums.length;if (target < nums[0] || target > nums[len - 1]) {return -1;}int left = 0, right = len;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return left;}//方法二：队列实现滑动窗口思想//先把数组中元素不停的入队，直到总和大于等于s为止，接着记录队列中元素的个数，然后再不停的出队，直到队列中元素的和小于s为止。//接着再把数组中的元素添加到队列中...重复上面的操作，直到数组中的元素全部用完为止//定义两个指针，分别指向队头和队尾//时间复杂度O(N)，空间复杂度O(1)private int minSubArrayLenII(int target, int[] nums) {if (nums == null || nums.length == 0) {return 0;}int left = 0;int right = 0;int min = Integer.MAX_VALUE;int sum = 0;while (right < nums.length) {//不断入队sum += nums[right++];while (sum >= target) {//更新结果min = Math.min(min, right - left);//出队sum -= nums[left++];}}return min == Integer.MAX_VALUE ? 0 : min;}//方法一：暴力解法//遍历数组，分别计算数组中从第i个元素开始的总和，如果出现大于等于s则比较其长度，得出最小值//时间复杂度O(N^2)，空间复杂度O(1)private int minSubArrayLenI(int target, int[] nums) {if (nums == null || nums.length == 0) {return 0;}int min = Integer.MAX_VALUE;for (int i = 0; i < nums.length; i++) {int sum = nums[i];if (sum >= target) {return 1;}for (int j = i + 1; j < nums.length; j++) {sum += nums[j];if (sum >= target) {min = Math.min(min, j + 1 - i);break;}}}return min == Integer.MAX_VALUE ? 0 : min;}
}