---

1508. 子数组和排序后的区间和

• 标签：数组、双指针、二分查找、前缀和、排序
• 难度：中等

题目链接

• 1508. 子数组和排序后的区间和 - 力扣

题目大意

描述：给定一个数组 $nums$，包含 $n$ 个正整数。计算所有非空连续子数组的和，将和排序后得到新数组 $sums$。给定 $left$ 和 $right$（$1$-based），求 $sums[left-1..right-1]$ 的和。

要求：返回结果对 $10^9 + 7$ 取模。

说明：

• $1 \le n \le 1000$。
• $1 \le nums[i] \le 100$。
• $1 \le left \le right \le n(n+1)/2 \le 5 \times 10^5$。

示例：

• 示例 1：

输入：nums = [1,2,3,4], n = 4, left = 1, right = 5
输出：13 
解释：所有的子数组和为 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。将它们升序排序后，我们得到新的数组 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 1 到 ri = 5 的和为 1 + 2 + 3 + 3 + 4 = 13 。

• 示例 2：

输入：nums = [1,2,3,4], n = 4, left = 3, right = 4
输出：6
解释：给定数组与示例 1 一样，所以新数组为 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下标从 le = 3 到 ri = 4 的和为 3 + 3 = 6 。

解题思路

思路 1：暴力

1. 核心思想

$n \le 1000$，子数组总数 $n(n+1)/2 \le 5 \times 10^5$。可以直接枚举所有子数组和，排序后取区间和。

2. 具体步骤

第 1 步：生成所有非空连续子数组的和。

第 2 步：排序。

第 3 步：对 $sums[left-1..right-1]$ 求和取模。

3. 举例说明

以 $nums = [1,2,3,4], left = 1, right = 5$ 为例：

所有子数组和：

• $[1]=1$，$[2]=2$，$[3]=3$，$[4]=4$
• $[1,2]=3$，$[2,3]=5$，$[3,4]=7$
• $[1,2,3]=6$，$[2,3,4]=9$
• $[1,2,3,4]=10$

排序后：$[1,2,3,3,4,5,6,7,9,10]$。

$left=1, right=5$：$1+2+3+3+4=13$。

思路 1：代码

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MOD = 10 ** 9 + 7
        sub_sums = []
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                sub_sums.append(s)

        sub_sums.sort()
        ans = sum(sub_sums[left - 1:right]) % MOD
        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n^2 \log n)$，生成 $O(n^2)$ 个和，排序 $O(n^2 \log n)$。
• 空间复杂度：$O(n^2)$。