Pythonで合計が等しいk個のサブ配列に分割できるかどうかを確認します

numsという数値の配列があり、別の値Kもあるとします。各サブ配列の要素の合計が等しくなるように、配列numsをK個の連続するサブ配列に分割できるかどうかを確認する必要があります。

したがって、入力がnums =[2、5、3、4、7] k =3のような場合、[（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
• 0からn-1の範囲のiの場合、do
  • 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）の場合、
    • ループから抜け出す
• カウントが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