LintCode 406: Minimum Size Subarray Sum (同向雙指針經典題!!!)

1. 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 -1 instead.

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.

Challenge

If you have figured out the O(nlog n) solution, try coding another solution of which the time complexity is O(n).

思路：同向雙指針

注意：

1. 凡是題目提到子串，子數組之類的，多考慮雙指針(可能同向，也可能反向);

2. 子串之類的題目有單調性，即超過某個就都滿足

   左邊不行右邊行 - 最短子串， 如此題

   左邊行右邊不行 - 最長子串， 如Longest Substring Without Repeating Characters ???

3. 同向雙指針模闆：右指針用for loop， 左指針嵌在for loop裡面用while loop。滿足條件時更新最大/小值，移動左指針并更新sum。
4. 注意while loop的條件是 sum>=s，即==s的情況也必須考慮。LintCode 386的while loop也是一樣。

代碼如下：

class Solution {
public:
    /**
     * @param nums: an array of integers
     * @param s: An integer
     * @return: an integer representing the minimum size of subarray
     */
    int minimumSize(vector<int> &nums, int s) {
        int len = nums.size();
        if (len == 0) return -1;
        
        int left = 0;
        int minLen = INT_MAX;
        int sum = 0;
        
        for (int right = 0; right < len; ++right) {
            sum += nums[right];
            while (sum >= s) {  //注意這裡是>=s，即==s的情況也考慮
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
    
        return (minLen == INT_MAX) ? -1 : minLen;
    }
};