O(n) C++ method


  • 0
    E
    class Solution {
    public:
        int minSubArrayLen(int s, vector<int>& nums) {
            for (int i = 1; i < nums.size(); ++i) nums[i] += nums[i - 1];
            if (nums.empty() || nums.back() < s) return 0;
            int start_index = -1, res = INT_MAX;
            for (int i = 0; i < nums.size(); ++i) {
                int tmp = nums[i] - (start_index == -1 ? 0 : nums[start_index]);
                while (tmp >= s) {
                    res = min(res, i - start_index);
                    if (res == 1) return 1;
                    ++start_index;
                    tmp = nums[i] - nums[start_index];
                }
            }
            return res == INT_MAX ? 0 : res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.