使用 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
以上是 使用 Python 查找已排序子数组和的范围和的程序 的全部内容， 来源链接： utcz.com/z/331775.html
