Time Cost

21min36s

Code

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = nums.size() + 1;
        // do the sum first
        vector<long long> sum(nums.size() + 1, 0); //sumn[0] = 0
        long long total = 0;
        for (int i=0; i<nums.size(); i++) {
            total += nums[i];
            sum[i+1] = total;
        }

        int base = 1, ceil = nums.size();
        int window = (base + ceil) / 2;
        bool isqualified = false;

        while (base <= ceil) {
            for (int i=0; i<=nums.size()-window; i++) {
                if (sum[i + window] - sum[i] >= target) {
                    result = window;
                    ceil = window - 1;
                    window = (base + ceil) / 2;
                    isqualified = true;
                    break;
                }
            }
            if (!isqualified) {
                base = window + 1;
                window = (base + ceil) / 2;
            }
            isqualified = false;
        }

        if (result == nums.size() + 1) {
            return 0;
        }

        return result;
    }
};