Minimum Size Subarray Sum
題意，給一個陣列與一個目標值，找出最少連續元素個數總和大於目標值。
解題思路：
可用暴力法枚舉所有可能性但需花 $$O(N^2)$$ 的時間複雜度，且含有許多重複運算的動作。
另外使用兩個指針方法來優化，一開始固定 i ，當未滿足條件時，不斷的移動 j ，一但滿足了條件，再慢慢移動 i 去縮短路徑長度。
public int minimumSize(int[] nums, int s) {
if (nums == null || nums.length == 0) {
return -1;
}
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i = 0, j = 0; i < nums.length; i++) {
while (j < nums.length && sum < s) {
sum += nums[j];
j++;
}
if (sum >= s) {
min = Math.min(min, j - i);
}
sum -= nums[i];
}
if (min == Integer.MAX_VALUE) {
return -1;
} else {
return min;
}
}
Time Complexity：$$O(2N) = O(N)$$，因 i 與 j 各需移動N次
網友 Grandyang 提供了以下 O(N) 解法的思路：
"這個解法要用到二分查找法，思路是，我們建立一個比原數組長一位的sums數組，其中sums[i]表示nums數組中[0, i - 1]的和，然後我們對於sums中每一個值sums[i]，用二分查找法找到子數組的右邊界位置，使該子數組之和大於sums[i] + s，然後我們更新最短長度的距離即可。"
Update [2019.8.10]
找到另一種方法較直觀，是先不斷移動右指針，而在tempSum大於S時才不斷調整左指針。
註：Leetcode現在更新為0為invalid result。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int minLength = Integer.MAX_VALUE;
int end = 0;
int tempSum = 0;
for (int l = 0, r = 0; r < nums.length; r++ ) {
tempSum += nums[r];
while (tempSum >= s) {
minLength = Math.min(minLength, r - l + 1);
tempSum -= nums[l++];
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}