在 Python 中檢查是否可以將陣列分成 k 個和相等的子陣列

假設我們有一個名為 nums 的數字陣列，還有一個值 K。我們必須檢查是否可以將陣列 nums 分成 K 個連續的子陣列，使得每個子陣列的元素和相等。

因此，如果輸入類似於 nums = [2, 5, 3, 4, 7] k = 3，則輸出將為 True，因為我們可以建立三個分割槽，例如 [(2, 5), (3, 4), (7)]，它們都具有相同的和 7。

為了解決這個問題，我們將遵循以下步驟：

  • n := nums 的大小
  • cumul_sum := nums 中所有元素的累積和
  • total_sum := cumul_sum[n - 1]
  • 如果 total_sum 不能被 k 整除，則
    • 返回 False
  • count := 0, pos := -1
  • 對於 i 從 0 到 n - 1，執行
    • 如果 pos 等於 -1，則
      • sub := 0
    • 否則，
      • sub := cumul_sum[pos]
    • 如果 cumul_sum[i] - sub 等於 (total_sum / K)，則
      • pos := i
      • count := count + 1
    • 否則，當 cumul_sum[i] - cumul_sum[pos] > (total_sum / K) 時，則
      • 退出迴圈
  • 當 count 等於 K 時返回 true，否則返回 false

示例

讓我們看看以下實現以更好地理解：

 即時演示

def solve(nums, k):
   n = len(nums)
   cumul_sum = [0 for i in range(n)]
   cumul_sum[0] = nums[0]
   for i in range(1, n):
      cumul_sum[i] = cumul_sum[i - 1] + nums[i]
   total_sum = cumul_sum[n - 1]
   if total_sum % k != 0:
      return False
   count = 0
   pos = -1
   for i in range(n):
      if pos == -1:
         sub = 0
      else:
         sub = cumul_sum[pos]
      if cumul_sum[i] - sub == total_sum / k:
         pos = i
         count += 1
      elif cumul_sum[i] - cumul_sum[pos] > total_sum / k:
         break
   return count == k
nums = [2, 5, 3, 4, 7]
k = 3
print(solve(nums, k))

輸入

[2, 5, 3, 4, 7], 3

輸出

True

更新於： 2021年1月19日

151 次檢視

開始您的 職業生涯

透過完成課程獲得認證

開始
廣告