My accepted 9ms c++ solution use a deque, O(n)


  • 0
    class Solution {
    public:
        int minSubArrayLen(int s, std::vector<int>& nums) {
    		int sum = 0, begin = 0;
    		std::size_t size = nums.size(), res = size + 1;
    		std::deque<int> d_num;
    		for (std::size_t i = 0; i != size; ++i) {
    			d_num.push_back(nums[i]);
    			sum += nums[i];
    			if (sum >= s) {
    				while (sum - d_num.front() >= s) {
    					sum -= d_num.front();
    					d_num.pop_front();
    				}
    				if (d_num.size() < res)
    					res = d_num.size();
    			}
    		}
    		return res == size + 1 ? 0 : static_cast<int>(res);
        }
    };

Log in to reply
 

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