美文网首页
[BinarySearch]209 Minimum Size S

[BinarySearch]209 Minimum Size S

作者: 野生小熊猫 | 来源:发表于2018-10-26 02:47 被阅读0次
  • 分类:BinarySearch

  • 考察知识点:BinarySearch/SlideWindow

  • 最优解时间复杂度:O(n)SlideWindow/O(nlogn)BinarySearch

  • 最优解空间复杂度:O(1)

209. 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).

代码:

O(n)方法:

class Solution:
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        #边界条件
        if len(nums)==0:
            return 0

        start=0
        sum_=0
        max_len=len(nums)
        len_=max_len+1
        for end in range(max_len):
            sum_+=nums[end]
            while sum_>=s and end-start>=0:
                len_=min(end-start+1,len_)
                sum_-=nums[start]
                start+=1

        if len_==max_len+1:
            return 0
        else:
            return len_

O(nlogn)方法:

class Solution:
    def minSubArrayLen(self, s, nums):
        """
        :type s: int
        :type nums: List[int]
        :rtype: int
        """
        #边界条件
        if len(nums)==0:
            return 0

        max_len=len(nums)
        sum_list=[0]
        len_=max_len+1

        for i in range(max_len):
            sum_list.append(sum_list[i]+nums[i])

        for i in range(max_len):
            start=-1
            end=i
            while end-start>=0:
                mid=(end-start)//2+start
                if sum_list[i+1]-sum_list[mid+1]>=s:
                    len_=min(len_,i-mid)
                    start=mid+1
                else:
                    end=mid-1

        if len_==max_len+1:
            return 0
        else:
            return len_

讨论:

1.这道题在Leetcode上被分到了BinarySearch里,题目要求把O(n)和O(nlogn)的方法都写一遍
2.reference:小Q刷Leetcode虽然我并没有怎么看懂他的思路

O(nlogn)方法 O(n)方法

相关文章

网友评论

      本文标题:[BinarySearch]209 Minimum Size S

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