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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習