在 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 次查看

开始您的 职业生涯

通过完成课程获得认证

开始
广告