给定一个长度为 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; } }
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; } }