美文网首页
209. Minimum Size Subarray Sum

209. Minimum Size Subarray Sum

作者: April63 | 来源:发表于2018-05-15 19:11 被阅读0次

这一题的思路是用两个指针来指示,start,end指针表示subarray,其中end指向subarray的后一位。首先end指针往后移动直到当前的subarray之和大于s,然后start指针完后移动直到最小的大于s值的情况,计算lenth,然后start后一一位,继续重复上述过程,代码如下:

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1 and nums[0] >= s:
            return 1
        start = 0
        end = 0
        min_len = len(nums)
        count = 0
        while end <= len(nums):
            while count < s and end <= len(nums):
                if end == len(nums) and start == 0 and count < s:
                    return 0
                if end < len(nums):
                    count += nums[end]
                end += 1
            while count > s:
                if count - nums[start] >= s and start < end:
                    count -= nums[start]
                    start += 1
                else:
                    break
            min_len = min(min_len, end - start)
            count -= nums[start]
            if start < len(nums) - 1:
                start += 1
        return min_len

相关文章

网友评论

      本文标题:209. Minimum Size Subarray Sum

      本文链接:https://www.haomeiwen.com/subject/jpuydftx.html