209. 长度最小的子数组
方法一:暴力法
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = nums.length + 1 ; int sublength = 0; int sum = 0; for(int i = 0;i < nums.length;i++){ sum = 0; for(int j = i;j < nums.length;j++){ sum += nums[j]; if(sum >= target){ sublength = j -i + 1; result = result < sublength ? result : sublength; break; } } } return result == nums.length + 1 ? 0 : result; } }
方法二:滑动窗口法
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE ; int left = 0,right=0; int sum = 0; while(right < nums.length){ sum += nums[right++]; while(sum >= target){ result = result < (right - left) ? result : (right - left); sum -= nums[left++]; } } return result == Integer.MAX_VALUE ? 0 : result; } }
方法三:二分法
class Solution { public int minSubArrayLen(int target, int[] nums) { int result = Integer.MAX_VALUE ; int[] sums = new int[nums.length + 1]; for(int i = 1;i <= nums.length;i++){ sums[i] = sums[i-1] + nums[i-1]; } for(int i = 0;i <= nums.length;i++){ int s = target + sums[i]; int index = Arrays.binarySearch(sums, s); if(index < 0){ index = ~index; } if(index <= nums.length){ result = result < index - i ? result : index - i; } } return result == Integer.MAX_VALUE ? 0 : result; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)