[LeetCode] 209. Minimum Size Subarray Sum
[LeetCode] 209. Minimum Size Subarray Sum
【原题】 Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.
【解释】 给定一个数组，要求求出这个数组的一个子数组大于等于给定s的最小长度，子数组要求连续。 【思路】 思路一、 由于要求连续，我们可以使用两个指针，left和right。主要两个步骤： 1. right右移。 若当前的sum小于s，说明目前的数字太少了，我们让right指针向右移以期让子数组有更多的数字使其和大于或等于s。 2. left右移。若找到了这样的子数组，接下来，我们逐渐缩小子数组的范围，即使得left右移，以期能够找到最小长度的子数组使得其和大于等于s，知道其和小于s则可停止移动left。 如此循环，直到right到达数组的边界。 这种方法是O(n)的时间复杂度。
public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int left=0,right=0;
int minLen=Integer.MAX_VALUE;
int sum=0;
while(right<nums.length){
while(sum<s&&right<nums.length)//步骤1
sum+=nums[right++];
while(sum>=s){//步骤2
minLen=Math.min(minLen, right-left);
sum-=nums[left++];
}
}
return minLen==Integer.MAX_VALUE?0:minLen;//若数组中不存在这样的子数组则返回零
//return minLen;
}
}思路二、 一般的题目要求更快的时间复杂度，然而这个题目要求在完成一个O(n)的算法之后，要求在找出一个O(nlogn)的算法，也是神奇。Anyway，没想出来。但了解一下不同的思路也算长长见识，参考这里
举个栗子来说说思路吧。 数组为[2,3,1,2,2,4,3], s=7 首先开辟一个比原数组多1的数组sums，保留[0,i-1]下标的和。这个例子中sums数组为:[0,2,5,6,8,12,15]。 然后用查找最小的>=s+sums[i]的index为right。 为什么要这样呢？这说明i到right的元素之和是>=s的啊，这不就是题目所要求的吗？如i==0的时候，最小的大于等于s的是8，index为4，这说明长度为4的子数组>=s，按照同样的思想找到最短的那一个长度就行了。由于sums是一个有序数组，所以复杂度中的logn就是二分查找的复杂度。
public class Solution {
public int binarySearch(int[] sums,int s,int cur){
int left=cur,right=sums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(sums[mid]>=s+sums[cur])
right=mid-1;
else left=mid+1;
}
return left;
}
public int minSubArrayLen(int s, int[] nums) {
int ans=nums.length+1;
int[] sums=new int[nums.length+1];
sums[0]=0;
for(int i=0;i<nums.length;i++)sums[i+1]=sums[i]+nums[i];
for(int i=0;i<sums.length;i++){
int right=binarySearch(sums,s,i);
if(right==nums.length+1) break;
ans=Math.min(ans, right-i);
}
return ans==nums.length+1?0:ans;
}}