1. 209

minimum-size-subarray-sum

2. 算法

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

http://blog.csdn.net/mijian1207mijian/article/details/51705273

2.1 滑动窗口法，

使用两个下标start和end标识窗口（子数组）的左右边界：O(n)

2.2 二分查找：O(nlgn)

3.代码

3.1

// O(n)

class Solution {

public:

    int minSubArrayLen(int s, vector<int>& nums) {

        if (nums.empty()) return 0;

        int left = 0, right = 0, sum = 0, len = nums.size(), res = len + 1;

        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 + 1 ? 0 : res;

    }

};

3.2

// O(nlgn)

class Solution {

public:

    int minSubArrayLen(int s, vector<int>& nums) {

        int len = nums.size(), sums[len + 1] = {0}, res = len + 1;

        for (int i = 1; i < len + 1; ++i) sums[i] = sums[i - 1] + nums[i - 1];

        for (int i = 0; i < len + 1; ++i) {

            int right = searchRight(i + 1, len, sums[i] + s, sums);

            if (right == len + 1) break;

            if (res > right - i) res = right - i;

        }

        return res == len + 1 ? 0 : res;

    }

    int searchRight(int left, int right, int key, int sums[]) {

        while (left <= right) {

            int mid = (left + right) / 2;

            if (sums[mid] >= key) right = mid - 1;

            else left = mid + 1;

        }

        return left;

    }

};