leetcode_c++：Minimum Size Subarray Sum (209)

題目

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 s = 7,

the subarray [4,3] has the minimal length under the problem constraint.

算法

O（N）

滑動視窗的形式

雙指針

http://www.cnblogs.com/grandyang/p/4501934.html

這道題給定了我們一個數字，讓我們求子數組之和大于等于給定值的最小長度，跟之前那道 Maximum Subarray 最大子數組有些類似，并且題目中要求我們實作O(n)和O(nlgn)兩種解法，那麼我們先來看O(n)的解法，我們需要定義兩個指針left和right，分别記錄子數組的左右的邊界位置，然後我們讓right向右移，直到子數組和大于等于給定值或者right達到數組末尾，此時我們更新最短距離，并且将left像右移一位，然後再sum中減去移去的值，然後重複上面的步驟，直到right到達末尾，且left到達臨界位置，即要麼到達邊界，要麼再往右移動，和就會小于給定值。代碼如下

// O(n)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if (nums.empty()) return ;
        int left = , right = , sum = , len = nums.size(), res = len + ;
        while (right < len) {
            while (sum < s && right < len) {
                sum += nums[right++];
            }
            while (sum >= s) {
                res = min(res, right - left);
                sum -= nums[left++];
            }
        }
        return res == len +  ?  : res;
    }
};
           

算法

二分鐘查找

O(NlgN)

下面我們再來看看O(nlgn)的解法，這個解法要用到二分查找法，思路是，我們建立一個比原數組長一位的sums數組，其中sums[i]表示nums數組中[0, i - 1]的和，然後我們對于sums中每一個值sums[i]，用二分查找法找到子數組的右邊界位置，使該子數組之和大于sums[i] + s，然後我們更新最短長度的距離即可。代碼如下：

// O(nlgn)
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size(), sums[len + ] = {}, res = len + ;
        for (int i = ; i < len + ; ++i) sums[i] = sums[i - ] + nums[i - ];
        for (int i = ; i < len + ; ++i) {
            int right = searchRight(i + , len, sums[i] + s, sums);
            if (right == len + ) break;
            if (res > right - i) res = right - i;
        }
        return res == len +  ?  : res;
    }
    int searchRight(int left, int right, int key, int sums[]) {
        while (left <= right) {
            int mid = (left + right) / ;
            if (sums[mid] >= key) right = mid - ;
            else left = mid + ;
        }
        return left;
    }
};