滑动窗口最小大小子数组和

Question

给定一个正整数数组 nums 和一个正整数 target，要求返回一个子数组的最小长度，这个子数组的和要大于或等于 target。如果没有这样的子数组，就返回 0。

例子 1:

输入:

target = 7, nums = [2,3,1,2,4,3]

输出: 2

解释:

子数组 [4,3] 是在这个问题限制下的最小长度的子数组。

我用滑动窗口的方法成功解决了这个问题，但我希望能得到一些帮助，以优化运行时间并生成输出。目前的时间复杂度是 O(n)。

class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        current_sum=nums[0]
        possible_combinations=[]
        result=float("inf")
        start=0
        end=0
        target_sum=target

        if sum(nums)<target:
            return 0
        elif target in nums:
            return 1
        else:
            while start < len(nums) and end < len(nums):
                if current_sum >= target_sum:
                    result=min(len(nums[start:end + 1]), result)
                    current_sum -= nums[start]
                    start += 1
                elif current_sum < target_sum:
                    end += 1
                    if end < len(nums):
                        current_sum += nums[end]
            if result ==float("inf"):
                return 0
        return result



        
        

Answer 1

你看到这个：len(nums[start:end + 1])，其实就是在计算 end - start + 1。

换句话说，你在不断地对 nums 进行切片操作，这其实是没必要的。

你可以这样写：

result = min(end - start + 1, result)

Answer 2

这里有两个主要的性能问题：

• 你可以去掉这一部分：

    if sum(nums)<target:
        return 0
    elif target in nums:
        return 1
  

  这段代码在每次运行时都会遍历你的数组两次，即使它可能只适用于很小一部分的测试情况。你的 while 循环已经处理了这些情况，虽然会花费更多的时间（所以可以测试一下效果，比如如果95%的测试情况都满足 sum(nums)<target，那么去掉这个边缘情况可能会让你的代码变慢）。

• 在

   result=min(len(nums[start:end + 1]), result)
  

  中，你为了获取子数组的长度而创建了一个副本，但其实你已经知道长度了：它是 end-start+1。所以你可以用以下代码替换它：

   result = min(end-start+1, result)
  

另外，如果结果是 1，你可能想提前结束循环，因为结果不可能再低了——不过这是否会影响性能还得看测试数据，或者这个额外的条件是否会增加平均运行时间：

while start < len(nums) and end < len(nums) and result != 1:

你可以减少一些比较操作，但这些可能只会对性能产生微小的影响（而且可能不会让代码更美观或更易读）。这里有一些例子：

• 你不需要测试 elif current_sum < target_sum，因为在 if current_sum >= target_sum 为假之后，这已经是唯一的选项了，所以可以直接用 else。

• 你可以把检查是否到达数组末尾的条件放到 else 块里（因为只有在那时 end 才会增加），这样就可以从 while 循环中去掉这个检查（这样在 start 增加时就节省了一次比较），例如可以写成：

   while start < len(nums) and result != 1:
       if current_sum >= target_sum:
           ...
       else:
           end += 1
           if end >= len(nums):
               break
           current_sum += nums[end]
  

• 同样，对于 start < len(nums) and result != 1 的测试，这个条件只有在 if 块中才有意义。

顺便提一下，你的函数目前在处理空列表时会出错（因为 current_sum=nums[0] 会失败）。虽然可能在某处规定了列表不能为空（尽管你的文档字符串没有说明），这似乎不会造成问题（直到它真的出问题），而修复这个问题很可能不会提高性能，但它会在代码审查中失败，所以你可能要记住这一点。