209. 长度最小的子数组

原题链接：

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/submissions/

完成情况：

解题思路：

//找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组

	 1 <= target <= 109
	 1 <= nums.length <= 105
	 1 <= nums[i] <= 105

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

定义两个指针 start\textit{start}start 和 end\textit{end}end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum\textit{sum}sum 存储子数组中的元素和（即从 nums[start]\text{nums}[\textit{start}]nums[start] 到 nums[end]\text{nums}[\textit{end}]nums[end] 的元素和）。

初始状态下，start\textit{start}start 和 end\textit{end}end 都指向下标 000，sum\textit{sum}sum 的值为 000。

每一轮迭代，将 nums[end]\text{nums}[end]nums[end] 加到 sum\textit{sum}sum，如果 sum≥s\textit{sum} \ge ssum≥s，则更新子数组的最小长度（此时子数组的长度是 end−start+1\textit{end}-\textit{start}+1end−start+1），然后将 nums[start]\text{nums}[start]nums[start] 从 sum\textit{sum}sum 中减去并将 start\textit{start}start 右移，直到 sum

参考代码：

__209长度最小的子数组_nlogn_n

package 日常Java程序测试.代码随想录.数组;

import java.util.Arrays;

public class __209长度最小的子数组_nlogn_n {
	public int minSubArrayLen(int target, int[] nums) {
		//找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组
		/**
		 1 <= target <= 109
		 1 <= nums.length <= 105
		 1 <= nums[i] <= 105

		 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
		 */
		int n = nums.length;
		if (n == 0){
			return 0;
		}
		int res = Integer.MAX_VALUE;
		int sums [] = new int[n + 1];   //每一个都对应前面所有nums[]的和。
		for (int i = 1;i<=n;i++){
			sums[i] = sums[i - 1] + nums[i-1];
		}
		for (int i = 1;i<=n;i++){
			int tar = target + sums[i-1];   //每一个合，都加上target
			int bound = Arrays.binarySearch(sums,tar);
			if (bound < 0){
				bound = -bound - 1;
			}
			if (bound <= n){
				res = Math.min(res,bound - (i-1));
			}
		}
		return res == Integer.MAX_VALUE ? 0 : res;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

__209长度最小的子数组_n_1

package 日常Java程序测试.代码随想录.数组;

public class __209长度最小的子数组_n_1 {
	/**
	 *
	 * @param target
	 * @param nums
	 * @return
	 */
	public int minSubArrayLen(int target, int[] nums) {
		int n = nums.length;
		if (n == 0){
			return 0;
		}
		int res = Integer.MAX_VALUE;
		int start = 0,end = 0;
		int sum = 0;
		while (end < n){
			sum += nums[end];
			while (sum >= target){
				res = Math.min(res,end - start + 1);
				sum -= nums[start];
				start++;
			}
			end++;
		}
		return res == Integer.MAX_VALUE ? 0 : res;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30