合計がPythonで与えられる2つの重複しないサブリストの長さの合計を見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、合計がkであるnums内の2つの重複しないサブリストを検索し、それらの長さの合計を検索する必要があります。可能なサブリストが3つ以上ある場合は、2つの最小のサブリストの長さの合計を見つける必要があります。答えが見つからない場合は、-1を返します。

したがって、入力がnums =[7、10、-2、-1、4、3] k =7の場合、[7]や[4、3]のようなサブリストを選択すると、出力は3になります。 。 [10、-2、-1]は長いので、選択しませんでした。

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

• N：=Aのサイズ

• サイズNのプレフィックス：=、無限大で埋める

• last：=キー0の値が-1のマップ{0：-1}

• s：=0

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

  • s：=s + A [i]

  • prefix [i]：=i − last [s − target]、見つからない場合はset −infinity

  • last [s]：=i

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

  • prefix [i]：=最小のprefix [i]、prefix [i − 1]

• サイズNの接尾辞：=、無限大で埋める

• last：=キー0の値がNのマップ{0：N}

• s：=0

• N − 1〜-1の範囲のiの場合、1ずつ減少します。

  • s：=s + A [i]

  • 接尾辞[i]：=last [s − target]（見つからない場合は無限集合を設定）− i

  • last [s]：=i

• N − 2〜-1の範囲のiの場合、1ずつ減少します。

  • 接尾辞[i]：=最小の接尾辞[i]と接尾辞[i + 1]

• ans：=0からN−1の範囲の各iのプレフィックス[i]+サフィックス[i+1]の最小値

• ans<無限大の場合はansを返します。それ以外の場合は-1

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

例

class Solution:
   def solve(self, A, target):
      INF = float("inf")
      N = len(A)
      prefix = [INF] * N
      last = {0: −1}
      s = 0
      for i in range(N):
         s += A[i]
         prefix[i] = i − last.get(s − target, −INF)
         last[s] = i
      for i in range(1, N):
         prefix[i] = min(prefix[i], prefix[i − 1])
      suffix = [INF] * N
      last = {0: N}
      s = 0
      for i in range(N − 1, −1, −1):
         s += A[i]
         suffix[i] = last.get(s − target, INF) − i
         last[s] = i
      for i in range(N − 2, −1, −1):
         suffix[i] = min(suffix[i], suffix[i + 1])
      ans = min(prefix[i] + suffix[i + 1] for i in range(N − 1))
      return ans if ans < INF else −1
ob = Solution()
nums = [7, 10, −2, −1, 4, 3]
k = 7
print(ob.solve(nums, k))

入力

[7, 10, −2, −1, 4, 3], 7

出力

3