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;
	}
}