Pythonで合計が0である最長のサブリストの長さを見つけるプログラム

したがって、入力がnums =[1、1、-1、1、1、-1、1、-1、1、-1]のような場合、最長のサブリストは[-1]であるため、出力は8になります。 、1、1、-1、1、-1、1、-1]その合計は0です。

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

• テーブル：=新しい空のマップ

• cs：=0、max_diff：=0

• 0からnums− 1のサイズのiの場合、実行します

  • cs：=cs + nums [i]

  • csが0と同じ場合、

    • max_diff：=最大i+1およびmax_diff

  • csがテーブルにある場合、

    • max_diff：=max_diffの最大値と（i − table [cs]）

  • それ以外の場合

    • table [cs]：=i

• max_diffを返す

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

例

class Solution:
   def solve(self, nums):
      table = {}
      cs = 0
      max_diff = 0
      for i in range(len(nums)):
         cs += nums[i]
         if cs == 0:
            max_diff = max(i + 1, max_diff)
         if cs in table:
            max_diff = max(max_diff, i − table[cs])
         else:
            table[cs] = i
      return max_diff
ob = Solution()
nums = [1, 1, −1, 1, 1, −1, 1, −1, 1, −1]
print(ob.solve(nums))

入力

[1, 1, −1, 1, 1, −1, 1, −1, 1, −1]

出力

8