使用 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

Arnab Chakraborty

更新于: 2021年5月29日

340 次查看

开启你的 职业生涯

完成课程后获得认证

开始学习