Pythonで配列を等しい合計のサブ配列に分割できる合計を見つけます

整数Aの配列があるとします。値sum[i]の場合、配列をsum sum [i]のサブ配列に分割できるように、sumのすべての値を見つける必要があります。配列を等しい合計のサブ配列に分割できない場合は、-1を返します。

したがって、入力がA =[2、4、2、2、2、4、2、6]のような場合、配列は次のサブ配列に分割できるため、出力は[6,8,12]になります。合計6、8、および12。これらは次のとおりです。[{2、4}、{2、2、2}、{4、2}、{6}] [{2、4、2}、{2、2 、4}、{2、6}] [{2、4、2、2、2}、{4、2、6

これを解決するには、次の手順に従います-

• n：=a

  のサイズ

• table：=サイズnで、0で埋められた配列

• table [0]：=a [0]

• 1からnの範囲のiの場合、実行します

  • table [i]：=a [i] + table [i-1]

• S：=table [n-1]

• my_map：=新しいマップ

• 0からnの範囲のiの場合、実行

  • my_map [table [i]]：=1

• 答え：=新しいセット

• 範囲1から（（S）の平方根）+ 1の整数部分のiの場合、do

  • S mod iが0と同じ場合、

    • is_present：=True

    • part_1：=i

    • part_2：=S/iの商

    • part_1からS+1の範囲のjについては、各ステップでpart_1ごとに更新します。

      • jがmy_mapにない場合は、

        • is_present：=False

        • ループから出てきます

    • is_presentがtrueで、part_1がSと同じでない場合、

      • 回答のadd（part_1）

    • is_present：=True

    • （S / i）からS + 1までの範囲の商のjについては、各ステップでS // i、do

      で更新します。

      • jがmy_mapにない場合は、

        • is_present：=False;

        • ループから出てきます

    • is_presentおよびpart_2がSと同じでない場合、

      • 回答のadd（part_2）

• 回答のサイズが0と同じ場合、

  • -1を返す

• 回答を返す

例

理解を深めるために、次の実装を見てみましょう-

from math import sqrt
def find_sum(a) :
   n = len(a)
   table = [0] * n
   table[0] = a[0]
   for i in range(1, n) :
      table[i] = a[i] + table[i - 1]
   S = table[n - 1]
   my_map = {}
   for i in range(n) :
      my_map[table[i]] = 1
   answer = set()
   for i in range(1, int(sqrt(S)) + 1) :
      if (S % i == 0) :
         is_present = True;
         part_1 = i
         part_2 = S // i
         for j in range(part_1 , S + 1, part_1) :
            if j not in my_map :
               is_present = False
               break
         if (is_present and part_1 != S) :
            answer.add(part_1)
         is_present = True
         for j in range(S // i , S + 1 , S // i) :
            if j not in my_map:
               is_present = False;
               break
         if (is_present and part_2 != S) :
            answer.add(part_2)
   if(len(answer) == 0) :
      return -1
   return answer
a = [2, 4, 2, 2, 2, 4, 2, 6]
print(find_sum(a))

入力

[2, 4, 2, 2, 2, 4, 2, 6]

出力

{8, 12, 6}