package LeetCode; public class LeetCode209 { // https://leetcode.com/problems/minimum-size-subarray-sum/description/ // 暴力解法 // 该方法在 Leetcode 中会超时！ // 时间复杂度: O(n^3) // 空间复杂度: O(1) public int minSubArrayLen(int s, int[] nums) { if (s <= 0 || nums == null) throw new IllegalArgumentException("Illigal Arguments"); int res = nums.length + 1; for (int l = 0; l < nums.length; l++) for (int r = l; r < nums.length; r++) { int sum = 0; for (int i = l; i <=r; i++) sum += nums[i]; if (sum >= s) res = Math.min(res, r - l + 1); } // 无解的情况 if (res == nums.length + 1) return 0; return res; } // 优化暴力解 // 时间复杂度: O(n^2) // 空间复杂度: O(n) public int minSubArrayLen2(int s, int[] nums) { if(s <= 0 || nums == null) throw new IllegalArgumentException("Illigal Arguments"); // sums[i]存放nums[0...i-1]的和 int[] sums = new int[nums.length + 1]; sums[0] = 0; for(int i = 1 ; i <= nums.length ; i ++) sums[i] = sums[i-1] + nums[i-1]; int res = nums.length + 1; for(int l = 0 ; l < nums.length ; l ++) for(int r = l ; r < nums.length ; r ++){ // 使用sums[r+1] - sums[l] 快速获得nums[l...r]的和 if(sums[r+1] - sums[l] >= s) res = Math.min(res, r - l + 1); } // 无解的情况 if(res == nums.length + 1) return 0; return res; } // 滑动窗口的思路 // 时间复杂度: O(n) // 空间复杂度: O(1) public int minSubArrayLen3(int s, int[] nums) { if(s <= 0 || nums == null) throw new IllegalArgumentException("Illigal Arguments"); int l = 0 , r = -1; // nums[l...r]为我们的滑动窗口 int sum = 0; int res = nums.length + 1; while(l < nums.length){ // 窗口的左边界在数组范围内,则循环继续 if(r + 1 < nums.length && sum < s) sum += nums[++r]; else // r已经到头 或者 sum >= s sum -= nums[l++]; if(sum >= s) res = Math.min(res, r - l + 1); } // 无解的情况 if(res == nums.length + 1) return 0; return res; } // 另外一个滑动窗口的实现, 仅供参考 // 时间复杂度: O(n) // 空间复杂度: O(1) public int minSubArrayLen4(int s, int[] nums) { if(s <= 0 || nums == null) throw new IllegalArgumentException("Illigal Arguments"); int l = 0 , r = -1; // [l...r]为我们的窗口 int sum = 0; int res = nums.length + 1; while(r + 1 < nums.length){ // 窗口的右边界无法继续扩展了, 则循环继续 while(r + 1 < nums.length && sum < s) sum += nums[++r]; if(sum >= s) res = Math.min(res, r - l + 1); while(l < nums.length && sum >= s){ sum -= nums[l++]; if(sum >= s) res = Math.min(res, r - l + 1); } } if(res == nums.length + 1) return 0; return res; } // 时间复杂度: O(nlogn) // 空间复杂度: O(n) // 二分搜索 public int minSubArrayLen5(int s, int[] nums) { if(s <= 0 || nums == null) throw new IllegalArgumentException("Illigal Arguments"); // sums[i]存放nums[0...i-1]的和 int[] sums = new int[nums.length + 1]; sums[0] = 0; for(int i = 1 ; i <= nums.length ; i ++) sums[i] = sums[i-1] + nums[i-1]; int res = nums.length + 1; for(int l = 0 ; l < nums.length - 1 ; l ++){ // Java类库中没有内置的lowerBound方法， // 我们需要自己实现一个基于二分搜索的lowerBound:) int r = lowerBound(sums, sums[l] + s); if(r != sums.length){ res = Math.min(res, r - l); } } if(res == nums.length + 1) return 0; return res; } // 在有序数组nums中寻找大于等于target的最小值 // 如果没有（nums数组中所有值都小于target），则返回nums.length private int lowerBound(int[] nums, int target){ if(nums == null /*|| !isSorted(nums)*/) throw new IllegalArgumentException("Illegal argument nums in lowerBound."); int l = 0, r = nums.length; // 在nums[l...r)的范围里寻找解 while(l != r){ int mid = l + (r - l) / 2; if(nums[mid] >= target) r = mid; else l = mid + 1; } return l; } public static void main(String[] args) { int[] nums = {2, 3, 1, 2, 4, 3}; int s = 7; System.out.println((new LeetCode209()).minSubArrayLen(s, nums)); } }