使用 Python 查找已排序子数组和的范围和的程序

假设我们有一个包含 n 个正元素的数组 nums。如果我们计算 nums 的所有非空连续子数组的总和，然后通过创建一个新的 n*(n+1)/2 个数字数组以非递减的方式对它们进行排序。我们必须在新数组中找到从索引左到索引右（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。

为了解决这个问题，我们将按照以下步骤操作 -

• 米：= 10^9 + 7

• n := 数字的大小

• a:= 一个新列表

• 对于 0 到 n - 1 范围内的 i，请执行

• 如果 i 与 j 相同，则

• 否则，

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

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

• 对于 i 到 n - 1 范围内的 j，执行

• 对列表排序 a

• sm:= a 的所有元素的总和[从索引 left-1 到右])

• 返回 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