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

Question

给定一个正整数 nums 数组和一个正整数目标，返回 a 的最小长度 子数组 其总和大于或等于目标。如果没有这样的子数组，则返回 0。

示例1：

输入：

目标 = 7，数字 = [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

有 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]

会失败）。它可能在某处被指定为非空（尽管不是由您的文档字符串指定），显然不会导致问题（直到它确实出现）并且修复它很可能不会提高性能，但它会使任何代码审核失败，因此您可能想要保留记在心里。