Yu's Coding Garden : leetcode Question: Minimum Size Subarray Sum

Yu's Coding Garden : leetcode Question: Minimum Size Subarray Sum

Pages Minimum Size Subarray Sum Given an array of n positive integers and a positive integer s, find the minimal length of a 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  Analysis: Here in this post we just implement O(n log n) solution using binary search. At first it took me so much time to design the binary search on the original data array, however it is neither a neat binary search algorithm nor pass the OJ time limits. Then from the problem description I found that "sum >= s" and word "subarray". In other words, this means we don't have to know each number, we just need to know the sum, and start/end positions (end-start leads to length). OK, so first step is to get the sum array "ss[ ]" , where ss[0] = 0, ss[1] = sum(nums[0..1]), ss[i] = sum(nums[0,i-1]). Then next step is to design the binary search. We know that for binary search,

Read full article from Yu's Coding Garden : leetcode Question: Minimum Size Subarray Sum