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.
click to show more practice.
More practice:If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Approach#1 Brute Force
Brute force方法就是兩個循環(huán)港谊，start和end指針之間的數(shù)加起來搅裙。復雜度O(n2)丰介，一次AC赊抖。沒毛病，老鐵区转。
/**
* O(n^2)
*/
public int minSubArrayLen0(int s, int[] nums) {
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= s) {
//Math.min..
minLen = j - i + 1 < minLen ? j - i + 1 : minLen;
break;
}
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
Approach #2 Sliding Window
我想了類似的題目比如subarray sum equals k弧满，523. Continuous Subarray Sum等等，都是用一個map儲存過往的值狮暑，然后要么減去k，要么mod k暇赤；所以這題我也想map心例，結果發(fā)現(xiàn)這個是要求>=一個值而不是一個精確值宵凌，有可能map不到啊鞋囊。跟567. Permutation in String類似用Sliding window，兩個指針瞎惫。
然后我就看答案了溜腐。O(n)做法像下面這樣，竟然不需要用map瓜喇。
兩層while挺益，乍看上去像是O(n2)，其實是O(n)乘寒。
而且望众，貌似用for不太方便，只能用while伞辛。
而且烂翰，subarray sum equals k那題用這個方法似乎不太可行。
/**
* O(n)
*/
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0)
return 0;
int minLen = Integer.MAX_VALUE;
int sum = 0;
int j = 0;
int i = 0;
while (j < nums.length) {
sum += nums[j++];
while (sum >= s) {
minLen = Math.min(minLen, j - 1 - i + 1);
sum -= nums[i++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen ;
}
approach3 binary search
另外貼一個O(nlogn)的解法蚤氏，我沒動手做了：
private int solveNLogN(int s, int[] nums) {
int[] sums = new int[nums.length + 1];
for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
int minLen = Integer.MAX_VALUE;
for (int i = 0; i < sums.length; i++) {
int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
if (end == sums.length) break;
if (end - i < minLen) minLen = end - i;
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
private int binarySearch(int lo, int hi, int key, int[] sums) {
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (sums[mid] >= key){
hi = mid - 1;
} else {
lo = mid + 1;
}
}
return lo;
}
As to NLogN solution, logN immediately reminds you of binary search. In this case, you cannot sort as the current order actually matters. How does one get an ordered array then? Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search.
--
明天做76題或者Maximum Size Subarray Sum Equals k（我發(fā)現(xiàn)AC后推薦的題目很準確甘耿。。）
