ToB企服应用市场:ToB评测及商务社交产业平台

标题: 力扣209.长度最小的子数组 [打印本页]

---

作者: 渣渣兔    时间: 2024-10-9 22:22
标题: 力扣209.长度最小的子数组
题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

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

 暴力解法：

1. class Solution {
2.     public int minSubArrayLen(int target, int[] nums) {
3.         int ans=Integer.MAX_VALUE;//最终结果
4.         int res=0;//每次遍历得到的值
5.         for(int i=0;i<nums.length;i++){
6.             int sum=0;
7.             for(int j=i;j<nums.length;j++){
8.                 sum+=nums[j];
9.                 if(sum>=target){
10.                     res=j-i+1;
11.                     if(res<ans){
12.                         ans=res;
13.                     }
14.                     break;
15.                 }
16.             }
17.         }
18.         return ans == Integer.MAX_VALUE? 0 : ans;
19.         // if(ans!=Integer.MAX_VALUE){
20.         //     return ans;
21.         // }else{
22.         //     return 0;
23.         // }
24.     }
25. }

复制代码

超时↑
滑动窗口（双指针）：

所谓滑动窗口，就是不断的调治子序列的起始位置和停止位置，从而得出我们要想的结果。
在暴力解法中，一个for循环为滑动窗口的起始位置，一个for循环为滑动窗口的停止位置
那么滑动窗口如何用一个for循环来完成这个操作呢？
首先要思考如果用一个for循环，那么应该表示滑动窗口的起始位置，还是停止位置。
如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的停止位置？此时难免再次陷入 暴力解法的怪圈。
只用一个for循环，那么这个循环的索引，肯定是表示滑动窗口的停止位置

1. class Solution {
2.     public int minSubArrayLen(int target, int[] nums) {
3.         //滑动窗口（双指针）
4.         int l=0,r=0,ans=Integer.MAX_VALUE,sum=0,res=0;
5.         for(r=0;r<nums.length;r++){
6.             sum+=nums[r];
7.             while(sum>=target){
8.                 res=r-l+1;
9.                 if(res<ans){
10.                     ans=res;
11.                 }
12.                 sum-=nums[l];
13.                 l++;
14.             }
15.         }
16.         return ans == Integer.MAX_VALUE? 0 : ans;
17.     }
18. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4