给定一个长度为 n 的整数数组,和一个目标值 k ,请你找出这个整数数组中和大于等于 k 的最短子数组的长度。如果不存在和大于等于 k 的子数组则输出 -1。
数据范围:数组长度满足 , , 数组中的值满足
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; } }
#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
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @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
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
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; } }