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).
题目标签：Array, Two Pointers, Binary Search
题目给了一个数组，和一个 s， 让我们找到一个 最短的连续子数组，它的数组之和大于等于 s。
题目说了两种方法：O(n) 和 O(n log n)
方法1： O(n) 利用 Two Pointers
设一个start 和一个 end，用sliding window， 一个窗口，start 到 end。
当 这个窗口的sum 小于 s 的时候，说明数字还不够大，需要更多数字，就延伸右边的 end 来得到更多数字；
当 这个窗口的sum 大于等于 s 的时候，说明 我们得到了一个 可能是答案的 window size，我们需要最小的。 然后把左边的start 向右延伸，继续寻找新的可能性。
Java Solution:
Runtime beats 24.17%
完成日期：09/04/2017
关键词：Array，Two Pointers
关键点：Sliding window 控制左右边界，来找到最小的符合要求的 window size
1 class Solution
2 {
3 public int minSubArrayLen(int s, int[] nums)
4 {
5 /* Solution 1: O(n)*/
6 if(nums.length == 0)
7 return 0;
8
9 int start = 0;
10 int end = 0;
11 int res = Integer.MAX_VALUE;
12 int sum = nums[start];
13
14 while(true)
15 {
16 if(sum < s)
17 {
18 // shift end to right one place
19 if(end + 1 == nums.length)
20 break;
21
22 sum += nums[++end];
23 }
24 else if(sum >= s)
25 {
26 // get the smaller size
27 res = Math.min(res, end - start + 1);
28
29 if(end == start)
30 break;
31
32 // shift start to right one place
33 sum -= nums[start++];
34 }
35 }
36
37 if(res == Integer.MAX_VALUE)
38 res = 0;
39
40 return res;
41 }
42 }
方法2：O(n log n) 利用 二分法来找到最小符合要求的 window size
要利用 binary search 的话，需要一个有序的数组，所以我们需要新设一个 原nums size + 1 的新 array sums， 把每一个从0 到 i （在nums中） 的sum 存入 新 array 的 index 1 到最后。
所以新的array 里， 从index 1 到最后的 每一个值 都是 原nums 相对应的 0 到 i 的sum。
原题例子：
nums 2 3 1 2 4 3 原 array
sums 0 2 5 6 8 12 15 新 array 第一个位置不用，后面每一个数字都是 nums 里相对应的sum值
在有了这个有序数组之后， 可以遍历新 array index 1 开始的每一个数字， 找到每一个最小的右边边界 (sums[i] + s) ，然后记录一个最小的window size 就可以了。
Java Solution:
Runtime beats 12.29%
完成日期：09/04/2017
关键词：Array，Binary Search
关键点：新建一个 ascending sums array 对应 nums array；
用二分法找到符合s要求的最小的window size
1 class Solution
2 {
3 public int minSubArrayLen(int s, int[] nums)
4 {
5 int[] sums = new int[nums.length + 1];
6
7 for (int i = 1; i < sums.length; i++)
8 sums[i] = sums[i - 1] + nums[i - 1];
9
10 int minLen = Integer.MAX_VALUE;
11
12 for (int i = 0; i < sums.length; i++)
13 {
14 int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
15
16 if (end == sums.length)
17 break;
18
19 if (end - i < minLen)
20 minLen = end - i;
21 }
22 return minLen == Integer.MAX_VALUE ? 0 : minLen;
23 }
24
25 public int binarySearch(int lo, int hi, int key, int[] sums)
26 {
27 while (lo <= hi)
28 {
29 int mid = (lo + hi) / 2;
30
31 if (sums[mid] >= key)
32 hi = mid - 1;
33 else
34 lo = mid + 1;
35
36 }
37 return lo;
38 }
39 }
参考资料：
https://discuss.leetcode.com/topic/13749/two-ac-solutions-in-java-with-time-complexity-of-n-and-nlogn-with-explanation
LeetCode 算法题目列表 - LeetCode Algorithms Questions List