使用 Python 查詢排序子陣列和的範圍和的程式

假設我們有一個包含 n 個正元素的陣列 nums。如果我們計算 nums 的所有非空連續子陣列的和，然後以非遞減的方式對它們進行排序，透過建立一個包含 n*(n+1)/2 個數字的新陣列。我們需要找到新陣列中從索引 left 到索引 right（1 索引）的數字之和，包含這兩個索引。答案可能非常大，因此返回結果模 10^9 + 7。

因此，如果輸入類似於 nums = [1,5,2,6] left = 1 right = 5，則輸出將為 20，因為這裡所有子陣列的和為 1、5、2、6、6、7、8、8、13、14，因此排序後，它們為 [1,2,5,6,6,7,8,8,13,14]，從索引 1 到 5 的元素之和為 1+5+2+6+6 = 20。

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

  • m := 10^9 + 7

  • n := nums 的大小

  • a:= 一個新的列表

  • 對於範圍從 0 到 n - 1 的 i，執行以下操作

    • 對於範圍從 i 到 n - 1 的 j，執行以下操作

      • 如果 i 與 j 相同，則


        • 在 a 的末尾插入 nums[j]

      • 否則，

        • 在 a 的末尾插入 ((nums[j] + a 的最後一個元素) mod m)

  • 對列表 a 進行排序

  • sm:= a[從索引 left-1 到 right] 的所有元素之和

  • 返回 sm mod m

讓我們看看以下實現，以便更好地理解 -

示例

 即時演示

def solve(nums, left, right):
   m = 10**9 + 7
   n = len(nums)
   a=[]
   for i in range(n):
      for j in range(i,n):
         if i==j:
            a.append(nums[j])
         else:
            a.append((nums[j]+a[-1])%m)
   a.sort()
   sm=sum(a[left-1:right])
   return sm % m
nums = [1,5,2,6]
left = 1
right = 5
print(solve(nums, left, right))

輸入

[1,5,2,6], 1, 5

輸出

20

更新於: 2021年5月29日

340 次檢視

開啟你的 職業生涯

完成課程後獲得認證

開始學習
廣告