双指针

class Solution { public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) return 0; int ans = Integer.MAX_VALUE; int start = 0, end = 0; int sum = 0; while (end < nums.length) { sum += nums[end]; while (sum >= s) { ans = Math.min(ans, end - start + 1); sum -= nums[start]; start++; } end++; } return ans == Integer.MAX_VALUE ? 0 : ans; } }

前缀和 + 二分查找

class Solution { public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) return 0; int ans = Integer.MAX_VALUE; // 计算前缀和 int[] sum = new int[nums.length + 1]; for (int i = 1; i <= nums.length; i++) { sum[i] = sum[i-1] + nums[i - 1]; } for (int i = 1; i <= nums.length; i++) { int target = s + sum[i-1]; int bound = Arrays.binarySearch(sum, target); if (bound < 0) { bound = -bound -1; } if (bound <= nums.length) { ans = Math.min(ans, bound - (i - 1)); } } return ans == Integer.MAX_VALUE ? 0 : ans; } }