Python程式：查詢將陣列分成三個子陣列的方法數

假設我們有一個名為nums的陣列，我們需要找到將此陣列nums劃分成好方法的數量。答案可能非常大，因此返回結果模10^9 + 7。這裡，如果陣列被分成三個非空的連續子陣列（從左到右），並且左側元素的和小於或等於中間部分元素的和，中間部分元素的和小於或等於右側部分元素的和，則該陣列劃分是好的。

因此，如果輸入類似於nums = [2,3,3,3,7,1]，則輸出將為3，因為存在三種不同的劃分方法。

  • [2],[3],[3,3,7,1]
  • [2],[3,3],[3,7,1]
  • [2,3],[3,3],[7,1]

為了解決這個問題，我們將遵循以下步驟：

  • n := nums的大小
  • m := 10^9+7
  • ss := 一個大小為(1+n)並填充0的陣列
  • 對於nums中的每個索引i和值val，執行：
    • ss[i] := ss[i-1] + val
  • r := 0, rr := 0, ans := 0
  • 對於l從1到n-2，執行：
    • r := r和l+1的最大值
    • 當r < n-1且ss[r] - ss[l] < ss[l]時，執行：
      • r := r + 1
    • rr := rr和r的最大值
    • 當rr < n-1且ss[n] - ss[rr+1] >= ss[rr+1] - ss[l]時，執行：
      • rr := rr + 1
    • 如果ss[l] > ss[r] - ss[l]，則
      • 跳出迴圈
    • 如果ss[r] - ss[l] > ss[n] - ss[r]，則
      • 進行下一次迭代
    • ans := (ans + rr - r + 1) mod m
  • 返回ans

示例

讓我們看看下面的實現以更好地理解：

def solve(nums):
   n, m = len(nums), 10**9+7
   ss = [0] * (1+n)
   for i, val in enumerate(nums, 1):
      ss[i] = ss[i-1] + val

   r = rr = ans = 0
   for l in range(1, n-1):
      r = max(r, l+1)
      while r < n-1 and ss[r]-ss[l] < ss[l]:
         r += 1
      rr = max(rr, r)
      while rr < n-1 and ss[n]-ss[rr+1] >= ss[rr+1]-ss[l]:
         rr += 1
      if ss[l] > ss[r]-ss[l]:
         break
      if ss[r]-ss[l] > ss[n]-ss[r]:
         continue
      ans = (ans+rr-r+1) % m
   return ans

nums = [2,3,3,3,7,1]
print(solve(nums))

輸入

[1,7,3,6,5]

輸出

3

更新於：2021年10月6日

649 次檢視

開啟您的職業生涯

完成課程後獲得認證

開始
廣告