【滑动窗口】之 长度最小的子数组
2023-12-23 20:07:43
209. 长度最小的子数组
暴力循环法:
public int minSubArrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = nums[i];
//只要有个元素 > 目标值 就返回最小长度1
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 - i + 1);
break;//终止本次内循环 相当于left指针右移
}
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
执行用时:150 ms, 在所有 Java 提交中击败了6.65%的用户
内存消耗:41.4 MB, 在所有 Java 提交中击败了24.27%的用户
滑动窗口:使用队列相加(实际上我们也可以把它称作是滑动窗口,这里的队列其实就相当于一个窗口)
①我们把数组中的元素不停的入队,直到总和大于等于 s 为止,接着记录下队列中元素的个数;
②然后再不停的出队,直到队列中元素的和小于 s 为止
③接着再把数组中的元素添加到队列中……重复上面的操作,直到数组中的元素全部使用完为止。
这里以 [2,3,1,2,4,3] 举例画个图来看下
上面画的是使用队列,但在代码中我们不直接使用队列,我们使用两个指针,刚开始都指向队头;
public int minSubArrayLen(int target, int[] nums) {
int min = Integer.MAX_VALUE;
int left=0,right=0;//left相当于出队,right相当于入队
int sum=0;
//当右指针指向队尾就结束
while (right<nums.length){
sum+=nums[right++];
while (sum>=target){
min=Math.min(min,right-left);//这里为什么不加一因为到下一行right已经+=1了
sum-=nums[left];//队首出队
left++;
}
}
return min == Integer.MAX_VALUE ? 0 : min;
}
文章来源:https://blog.csdn.net/m0_48904153/article/details/135169080
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!