leetcode209 -- Minimum Size Subarray Sum

leetcode209 -- Minimum Size Subarray Sum

题目

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n). 

这个题的意思是找到最短的子数组,使得连续子数组的和不小于给定的数s。返回这个最短子数组的长度,如果没有的话就返回0.

法一.

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        # two pointers
        
        left, right =0,-1
        
        summ = 0
        
        res = len(nums)+1
        while left<len(nums):
            if right+1<len(nums) and summ<s:   # right is last one
                right += 1   # now 
                summ += nums[right]
                
            else:
                summ -= nums[left]
                left += 1
                
            if summ>=s:
                res = min(res,  right-left+1)
                
        if res==len(nums)+1:
            return 0
        
        return res

还是下成下面的这种形式更容易理解

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        # two pointers
        
        left, right =0, 0
        
        summ = 0
        
        res = len(nums)+1
        while left<len(nums):
            if summ>=s:
                res = min(res,  right-left)
                
            if right<len(nums) and summ<s:   
                summ += nums[right]
                right += 1
                
            else:
                summ -= nums[left]
                left += 1
                
            
                
        if res==len(nums)+1:
            return 0
        
        return res

写的再好理解一些就是

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        # two pointers
        
        left, right =0, 0
        
        summ = 0
        
        res = len(nums)+1
        while left<len(nums):
            if summ>=s:
                res = min(res,  right-left)
             
            if right<len(nums) and summ<s:   
                summ += nums[right]
                right += 1
            elif right ==len(nums) and summ<s:
                summ -= nums[left]
                left += 1
            elif right<len(nums) and summ>=s:
                summ -= nums[left]
                left += 1
            elif right == len(nums) and summ>=s:
                summ -= nums[left]
                left += 1
                   
        if res==len(nums)+1:
            return 0
        
        return res

或者

class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        # two pointers
        
        left, right =0, 0
        
        summ = 0
        
        res = len(nums)+1
        while left<len(nums):
            if summ>=s:
                res = min(res,  right-left)
                summ -= nums[left]
                left += 1
                
            elif right<len(nums) and summ<s:   
                summ += nums[right]
                right += 1
                
            else:
                summ -= nums[left]
                left += 1
            
                   
        if res==len(nums)+1:
            return 0
        
        return res

或者


class Solution(object):
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        
        # two pointers
        
        left, right =0, 0
        
        summ = 0
        
        res = len(nums)+1
        while left<len(nums):
            if summ>=s:
                res = min(res,  right-left)
      
            if summ >=s or (summ<s and right==len(nums)):
                summ -= nums[left]
                left += 1                
            else:
                summ += nums[right]
                right += 1
                
        if res==len(nums)+1:
            return 0
        
        return res

就以最后一个为例来说明, 意思就是用两个指针来代表这个窗口的区间,循环结束的条件是l<len(nums),然后每次进来都先比较当前的和是不是大于等于s,如果是的话,就更新最小的长度,然后再判断啥时候该是左边移,啥时候该右边的移。

因为我们要找的是和大于等于s的最小的连续子数组的长度,所以只要和大于等于s了,我们就该停止,同时把最左边的去掉,然后往后再继续求和找最短的,所以当和summ>=s的时候left就该加1, 还有一种情况,即当右边的指针走到头了,但是这时候和小于s这时候无论如何左边的也得不断地往右走,不然的话left就出不来了。其他情况都应该是右边的往右移。

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦