0%

LeetCode No.209 长度最小的子数组

LeetCode No.209 长度最小的子数组

LeetCode No.209 长度最小的子数组

题目详情

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的连续子数组,返回 0。

示例:

1
2
3
输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

1
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

题解

最常规的暴力解法,首先把nums数组中的所有数值全部加起来,如果小于s的话就返回0。之后两个for循环从头开始遍历,第一个for循环固定一个数字i,内部的循环从i开始往下用遍历j遍历并累加,加到数据大于s后就比较并存储这个j-i+1为当前最小的子数组,并退出内循环。

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
public static int minSubArrayLen(int s, int[] nums) {
int sum = 0;
int res = nums.length;
for (int num : nums) {
sum += num;
}
if (s > sum) {
return 0;
}
for (int i = 0; i < nums.length; i++) {
sum = 0;
sum += nums[i];
if (sum >= s) {
return 1;
}
for (int j = i + 1; j < nums.length; j++) {
sum += nums[j];
if (sum >= s) {
if (res > j - i + 1) {
res = j - i + 1;
}
}
}
}
return res;
}

但是暴力解法时间空间上就会很惨,807ms第一次见…

显然这个方法并不可取。

优化

使用队列的先进先出特性,只用一个for循环求解。

首先我们需要两个指针,第一个指向队列的头,另一个指向队列的尾。我们把nums中的元素不断加入到队列(也就是这里的假队列sum)中,同时移动队尾指针。当sum的值大于s后停止添加数据,存下当前的队首和队尾指针的距离(此距离就是当前长度最小子数组的长度),并让队列中的数据出队,移动队首指针。当队列里的数据和小于s后再继续数据入队…..重复上面的操作。每次存距离的时候都会和存下的最小距离进行比较,只保留最小值。

输入:s = 7, nums = [2,3,1,2,4,3]进行算法分析:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//首先我们从nums的第一个数开始入队
//循环入队.....(省略一堆入队)
//队列数据和大于等于s后停止入队,队列数据内容为
队尾--> 2 1 3 2 <--队首
//此时存最短长度为4,开始出队

队尾--> 2 1 3 <--队首
//此时从队首出队2后,队列数据值的和小于s,继续入队。

队尾--> 4 2 1 3 <--队首
//此时存最短长度4,开始出队

队尾--> 4 2 1 <--队首
//此时4+2+1仍然大于等于s,存下最短长度为3,继续出队。

队尾--> 4 2 <--队首
//此时4+2小于s 开始入队

队尾--> 3 4 2 <--队首
//此时最短长度为3,和之前的相同, 开始出队

队尾--> 3 4 <--队首
//此时 3+4大于等于s,最短长度为2,进行更新,nums数据遍历完了,最终的解就是2。

代码

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
public static int minSubArrayLen(int s, int[] nums) {
int res = Integer.MAX_VALUE;
// sum用来模拟队列
int sum = 0;
//队首和队尾指针
int head1 = 0;
int head2 = 0;

//队列入队出队循环
while (head1 < nums.length) {
//入队
sum += nums[head1++];
while (sum >= s) {
//记录值
res = Math.min(res, head1 - head2);
//出队
sum -= nums[head2++];
}
}
if (res == Integer.MAX_VALUE) {
return 0;
} else {
return res;
}
}




======================
全 文 结 束    感 谢 阅 读
======================