首页 > 试题广场 >

长度最小的连续子数组

[编程题]长度最小的连续子数组

热度指数：4167 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组 nums 和一个正整数 target , 找出满足和大于等于 target 的长度最短的连续子数组并返回其长度，如果不存在这种子数组则返回 0。

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的元素满足 $1 \le val \le 10^5 \$ ， $1 \le target \le 10^5 \$

示例1

输入

[1,2,4,4,1,1,1],9

输出

示例2

输入

[1,4,4,4,1,1,1],3

输出

算法知识视频讲解

唐氏综合征

老问题了，滑动窗口最简单：

  public static int minSubarray(int[] nums, int target) {
        // 使用滑动窗口
     int left = 0, right = 0, currRes = 0, res = Integer.MAX_VALUE;
        while (right < nums.length) {
            currRes += nums[right];
            while (currRes >= target) {
                res = Math.min(res, right - left + 1);
                currRes -= nums[left];
                left++;
            }
            right++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

发表于 2024-05-10 13:13:20 回复(0)

C++

pein531

双指针控制窗口端点，当窗口内元素的和小于目标时就扩张右边界，否则收缩左边界并更新长度。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int minSubarray(vector<int>& nums, int target) {
        // write code here
        int left = 0, right = 0, sum = 0, minLen = nums.size();
        while(right < nums.size()){
            sum += nums[right++];
            while(left < right && sum >= target){
                minLen = min(minLen, right - left);
                sum -= nums[left++];
            }
        }
        return minLen;
    }
};

发表于 2021-12-15 18:01:03 回复(0)

Python3

偶就要搞开发

滑

class Solution:
    def minSubarray(self, nums: List[int], target: int) -> int:
        # write code here
        min_len = 1000000
        i = 0
        j = -1
        sum = 0
        while j < len(nums):
            if sum < target:
                j += 1
                if j == len(nums): break
                sum += nums[j]
            else:
                min_len = min(min_len, j - i + 1)
                sum -= nums[i]
                if i == j:
                    i += 1
                    j += 1
                else:
                    i += 1
        return 0 if min_len == 100000 else min_len

发表于 2024-07-20 15:50:39 回复(0)

Python3

liangzhengjie

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:
    def minSubarray(self , nums: List[int], target: int) -> int:
        # write code here
        left = 0
        right = 0
        sum = 0

        min_len = len(nums)
        found = False

        # 采用左闭右开的方式
        while left < len(nums):
            # sum不够则伸长
            if sum < target:
                if right < len(nums):
                    sum += nums[right]
                    right += 1
                else:
                    break
            # 查看值并开始缩减长度
            else:
                found = True

                min_len = min(min_len, right - left)
                sum -= nums[left]
                left += 1
        
        if found:
            return min_len
        else:
            return 0

编辑于 2024-04-24 22:02:25 回复(0)

Python3

响亮的闵玆

class Solution:

def minSubarray (self, nums, s: int) -> int:

l = len(nums)

left = 0

right = 0

min_len =l

cur_sum = 0 # 当前的累加值

while right < l:

cur_sum += nums[right]

while cur_sum >= s: # 当前累加值大于目标值

min_len = min(min_len, right - left + 1)

cur_sum -= nums[left]

left += 1

right += 1

return min_len

编辑于 2024-02-03 23:59:14 回复(0)

Java

梁山教父

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int minSubarray (int[] nums, int target) {
        // write code here
        if(nums.length==0){
            return -1;
        }
        ArrayList<Integer> maxArr=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            int sum=0;
            int size=0;
            for(int j=i;j<nums.length;j++){
                if(sum<target){
                    sum+=nums[j];
                    size++;
                }
                if(sum>=target){
                    maxArr.add(size);
                    break;
                }
            }
        }
        int length=Collections.min(maxArr);
        return length;
    }
}

发表于 2023-05-20 09:17:09 回复(0)

在写面经的咸鱼很机智

// C语言竟然没人提交,那我来个代码,仿生态模式滑窗思维

int minSubarray(int* nums, int numsLen, int target ) {

// write code here
    int resultA = 0, resultE= 0;
    int resultLength = 0,resultLengthMin = 1000000;
    int i,j,k,sum = 0;

    for(i = 0; i < numsLen; ++i) {
        sum += nums[i];
        if(sum >= target) {
            resultE = i;

            resultLength = resultE - resultA + 1;
            if(resultLengthMin > resultLength) {
                resultLengthMin = resultLength;
            }

            for(j = resultA; j < i; ++j) {
                sum -= nums[j];
                if(sum >= target) {
                    resultA = j + 1;
                    resultLength = resultE - resultA + 1;
                    if(resultLengthMin > resultLength) {
                        resultLengthMin = resultLength;
                    }
                }
                else {
                    // 不能减,切记复原
                    sum += nums[j];
                    break;
                }
            }

        }
    }

    return (resultLengthMin>=100000?0:resultLengthMin);
}

发表于 2023-05-17 02:58:41 回复(0)

小谷围做题家

package main
import _"fmt"
import "math"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
*/
func minSubarray( nums []int ,  target int ) int {
    ans:=math.MaxInt32
    sum:=0
    var l,r int
    for i,x:=range nums{
        if sum+x<target{
            sum+=x
        }else{
            r=i
            break
        }
    }
    for ;r<len(nums);r++{
        sum+=nums[r]
        for sum>=target{
            if r-l+1<ans{
                ans=r-l+1
            }
            sum-=nums[l]
            l++
        }
    }
    if ans==math.MaxInt32{
        return 0
    }
    return ans
}

发表于 2023-03-11 17:30:30 回复(0)

寄了的突尼斯海怪很爱刷美剧

class Solution:
    def minSubarray(self , nums: List[int], target: int) -> int:
        # write code here
        n = []
        for i in range(len(nums)):
            sumn = 0
            for j in range(i,len(nums)):
                if sumn < target :
                    sumn += nums[j]
                if sumn >= target :
                    n.append(j + 1 - i)
                    break
        return(min(n))

发表于 2022-11-27 10:47:38 回复(0)

Python3

牛客867187861号

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# @param nums int整型一维数组

# @param target int整型

# @return int整型

class Solution:

def minSubarray(self , nums: List[int], target: int) -> int:

# write code here

n = len(nums)

res = n

slow = 0

fast = 0

sums = 0

if not nums:

return 0 #排除特殊情况

for i in range(n):

sums += nums[i]

if sums < target:

return 0 #排除特殊情况

sums = 0

while fast < n:

sums += nums[fast]

fast += 1

while slow < fast and sums >= target:

res = min(res,fast - slow)

sums -= nums[slow]

slow += 1

return res

发表于 2022-09-16 09:32:24 回复(0)

C++

阿金要努力

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int minSubarray(vector<int>& nums, int target) 
    {
        // write code here
        int start=0, end=0;
        int arrlen=INT_MAX, sum=0;
        while(end<nums.size())
        {
            sum+=nums[end];
            while(sum>=target)
            {
                arrlen=min(arrlen, end-start+1);
                sum-=nums[start++];
            }
            end++;
        }
        return arrlen==INT_MAX?0:arrlen;
    }
};

发表于 2022-09-08 02:30:54 回复(0)

Java

菲尼克斯弗兰克

// 考虑用滑动窗口处理很快！
public int minSubarray (int[] nums, int target) {
    int left = 0, right = 0, sum = 0, min = nums.length;
    while (right < nums.length) {
        int in = nums[right];
        right++;
        sum += in;
        while (sum >= target) {
            min = Math.min(min, right - left);
            int out = nums[left];
            left++;
            sum -= out;
        }
    }
    return min == nums.length ? 0 : min;
}

发表于 2021-12-11 11:46:10 回复(0)