Python 中检查数组中是否存在具有给定乘积的子数组

假设我们有一个名为 nums 的数组，它包含正数和负数。我们还有另一个值 k。我们必须检查数组中是否存在乘积为 k 的任何子数组。

因此，如果输入类似于 nums = [-2,-1,1,3,5,8]，k = 6，则输出将为 True，因为子数组为 [-2,-1,3]

为了解决这个问题，我们将遵循以下步骤：

• minimum := nums[0]，maximum := nums[0]
• prod_max := nums[0]
• 对于 i 从 1 到 nums 大小 - 1，执行
  • 如果 nums[i] < 0，则
    • 交换 maximum 和 minimum
  • maximum := nums[i] 和 (maximum * nums[i]) 中的最大值
  • minimum := nums[i] 和 (minimum * nums[i]) 中的最小值
  • 如果 minimum 或 maximum 等于 k，则
    • 返回 True
  • prod_max := prod_max 和 maximum 中的最大值
• 返回 False

让我们看看下面的实现以获得更好的理解：

示例代码

在线演示

def solve(nums, k):
   minimum = nums[0]
   maximum = nums[0]
 
   prod_max = nums[0]
 
   for i in range( 1, len(nums)):
      if nums[i] < 0:
         maximum, minimum = minimum, maximum

      maximum = max(nums[i], maximum * nums[i])
      minimum = min(nums[i], minimum * nums[i])

      if minimum == k or maximum == k:
         return True
 
      prod_max = max(prod_max, maximum)
   return False

nums = [-2,-1,1,3,5,8]
k = 6
print(solve(nums, k))

输入

[-2,-1,1,3,5,8], 6

输出

True

Arnab Chakraborty

更新于: 2021年1月15日

521 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习