leetcode-209:长度最小的子数组

简介: 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

解题

用暴力遍历也是可以解决的,但是python语言在leetcode上会超时

方法一:双指针(滑动窗口

python解法

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        n = len(nums)
        fast = 0
        slow = 0
        ans = n+1
        tmp = 0
        while fast<n:
            tmp+=nums[fast]
            while tmp>=s:
                ans = min(ans,fast-slow+1)#由于前面nums[fast]加上了,但是fast还没+1,所以这里要补个1
                tmp-=nums[slow]
                slow+=1
            fast+=1
        return 0 if ans==n+1 else ans       

c++解法

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int slow=0,fast=0;
        int res=INT_MAX;
        int tmp=0;
        while(fast<n){
            tmp+=nums[fast];
            while(tmp>=target){
                res = min(res,fast-slow+1);
                tmp-=nums[slow];
                slow++;
            }
            fast++;
        }
        return res==INT_MAX?0:res;
    }
};

java解法

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length;
        int slow=0,fast=0;
        int res=n+1;
        int cur=0;
        while(fast<n){
            cur+=nums[fast];
            while(cur>=target){
                res=Math.min(res,fast-slow+1);
                cur-=nums[slow];
                slow++;
            }
            fast++;
        }
        return res==n+1?0:res;
    }
}


相关文章
|
30天前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
3天前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
6 1
|
24天前
|
人工智能
力扣100114. 元素和最小的山形三元组 II(中等)
力扣100114. 元素和最小的山形三元组 II(中等)
|
30天前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
15 0
|
30天前
leetcode代码记录(长度最小的子数组
leetcode代码记录(长度最小的子数组
18 0
|
30天前
【力扣】209. 长度最小的子数组
【力扣】209. 长度最小的子数组
|
30天前
|
算法 测试技术
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
每日一题:LeetCode-209. 长度最小的子数组(滑动窗口)
|
30天前
|
算法
LeetCode题:581. 最短无序连续子数组,242. 有效的字母异位词,202. 快乐数
LeetCode题:581. 最短无序连续子数组,242. 有效的字母异位词,202. 快乐数
32 0
|
30天前
代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组
代码随想录 Day44 动规12 LeetCode T300 最长递增子序列 T674 最长连续递增序列 T718 最长重复子数组
46 0
|
18天前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
22 2
【力扣刷题】两数求和、移动零、相交链表、反转链表