我要招人

去企业版

首页 > 试题广场 >

和大于等于K的最短子数组

[编程题]和大于等于K的最短子数组

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

给定一个长度为 n 的整数数组，和一个目标值 k ，请你找出这个整数数组中和大于等于 k 的最短子数组的长度。如果不存在和大于等于 k 的子数组则输出 -1。

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ， $1 \le k \le 10^9 \$ ，数组中的值满足 $1\le num_i \le 10^5 \$

示例1

输入

[2,1,2,3],5

输出

示例2

输入

[2,3,4,5],16

输出

-1

算法知识视频讲解

Java

何东亚

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型ArrayList 
     * @param k int整型 
     * @return int整型
     */
    public int shortestSubarray (ArrayList<Integer> nums, int k) {
        // write code here
        // 数组长度
        int len = nums.size();
        // 定义左指针、右指针、和、最小长度
        // 最先长度初始值比len大
        int left = 0, right = 0, sum = 0, min = len + 1;
        // 右指针没走到头，就一直遍历
        while (right < len) {
            // 右指针走过的数累加到sum
            sum += nums.get(right);
            // 一旦sum>=target，就不断地走左指针
            while (sum >= k) {
                // 更新最小值
                // console.log(sum,min,right,left,right-left + 1)
                min = min < right - left + 1 ? min : right - left+1;
                // 先将左指针指的数移出sum，再将左指针右移1
                sum -= nums.get(left);
                left++;
            }
            // 不符合条件了，就继续走右指针
            right++;
        }
        // 若min变化过，则肯定不满足min > len，返回min
        // 没变化过，代表遍历完后没有找到符合条件的，返回0
        return min > len ? -1: min;

    }
}

编辑于 2024-03-26 23:10:05 回复(0)

听风尘

最短子数组没有说是连续子数组，所以双指针方法好像行不通，感觉排序，从大到小取数判断就行了

发表于 2023-10-17 11:22:09 回复(1)

fatzard

#include <algorithm>
#include <vector>
#define in long long
class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int len=nums.size();
        vector<in>sum(len);
        sum[0]=nums[0];
        for(int i=1;i<len;i++)
        {
            sum[i]=sum[i-1]+nums[i];
        }
        if(sum[len-1]<k)return -1;
        int ans=len;
        for(int i=len-1;i>=0;i--)
        {
            in target=sum[i]-k;
            if(target<0)break;
            int index=lower_bound(sum.begin(),sum.end(), target)-sum.begin();
            if(sum[index]>target){
                index--;
            }
            ans=min(ans,i-index);
        }
        return ans;
    }
};

前缀和+二分 C/C++注意小心爆int

发表于 2023-10-11 17:45:20 回复(0)

Java

Sun-light-Shell

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型ArrayList
* @param k int整型
* @return int整型
*/
public int shortestSubarray (ArrayList<Integer> nums, int k) {
long[] pre = new long[nums.size()];
int sub = nums.size()+1;
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) >= k) {
return 1;
}
if (i == 0) {
pre[i] = nums.get(i);
} else {
pre[i] = pre[i - 1] + nums.get(i);
}

if (pre[i] >= k) {
//判断最后一个前缀和，如果该元素大于等于k，但前一个小于k，则返回全长
if (i == (nums.size() - 1) && pre[i -1] < k) {
return nums.size();
}
for (int j = i - 2; j >= 0; j--) {
if (pre[i] - pre[j] >= k) {
sub = Math.min(sub, i - j);
break;
}
}
}

}
return sub == nums.size() + 1 ? -1:sub;
}
}

发表于 2023-05-22 17:05:48 回复(0)

Python3

Lxyapc

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

        # 解题思路：
        # 数组中的值满足 1 <= num <= 100000，都大于0，不需要考虑负数
        # 使用双指针，左右指针都从0开始，sum初值为nums[0]
        # 如果sum >= k，则左指针右移，sum减掉最左边的数字，寻找更短的数组
        # 否则，右指针右移，sum加上右边的数字，以满足 sum>=k
        # 如果右指针超界，说明没有继续搜索的必要，直接跳出，提高效率
        # 如果左指针超过右指针，说明找到单独一个数字大于k，结果为1，不必再判断其余
        # 最后返回结果

        sum = nums[0]
        left = 0
        right = 0
        size = len(nums)
        result = size + 1

        while left < size and left <= right:
            if sum >= k:
                result = min(result,right-left+1)
                sum -= nums[left]
                left += 1
            else:
                right += 1
                if right >= size:
                    break
                sum += nums[right]
         
        result = result if result <= size else -1
        return result

发表于 2023-04-29 01:32:17 回复(0)

牛客808686245号

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        minLen = float("inf")
        p = 0
        sum = 0
        for i in range(len(nums)):
            sum += nums[i]
            if sum >= k:
                while sum >= k:
                    sum -= nums[p]
                    p += 1
                minLen = min(minLen, i - p + 2)
        return -1 if minLen > len(nums) else minLen

发表于 2022-09-23 22:39:07 回复(0)

C++

大胆的香菇许愿简历通过

题目的等级是不是定错了🤣

发表于 2022-08-12 09:27:07 回复(0)

Java

skwan

经典双指针

import java.util.*;


public class Solution {
    public int shortestSubarray (int[] nums, int k) {
        int n = nums.length, sum = 0, left = 0, right = 0, ans = n + 1;
        while(right < n) {
            while(right < n && sum < k) {
                sum += nums[right];
                right++;
            }
            while(left < right && sum >= k) {
                ans = Math.min(ans, right - left);
                sum -= nums[left];
                left++;
            }
        } 
        return ans == n+1 ? -1 : ans;
    }
}

发表于 2022-06-20 21:01:05 回复(0)