老规矩先使用暴力破解方法,穷举每一种可能的起点,然后累加直到大于等于target。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(),ans = INT_MAX;
        if(n == 0) return 0;
        for(int i = 0;i < n;i++)
        {
            int sum = 0;
            for(int j = i;j < n;j++)
            {
                sum += nums[j];
                if(sum >= target)
                {
                    ans = min(ans,j - i + 1);
                    break;
                }     
            }
        }
        
        return (ans == INT_MAX) ? 0 : ans;
    }
};

运行效率仅击败5%:

Runtime: 808 ms, faster than 5.04% of C++ online submissions for Minimum Size Subarray Sum.
Memory Usage: 10.5 MB, less than 83.27% of C++ online submissions for Minimum Size Subarray Sum.

双指针法,非常巧妙

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int l = 0,r = 0,n = nums.size(),res = INT_MAX;
        int sum = 0;
        while(r < n) {
            sum += nums[r++];
            while(sum >= target){
                //上面r++,因此长度是r-l
                res = min(res,r-l);
                sum -= nums[l++];
            }
        }
        return (res == INT_MAX) ? 0:res;
    }
};

时间复杂度O(n),运行效率:

Runtime: 8 ms, faster than 90.20% of C++ online submissions for Minimum Size Subarray Sum.
Memory Usage: 10.6 MB, less than 59.31% of C++ online submissions for Minimum Size Subarray Sum.