Medium

题目描述

给你一个由 n 个正整数组成的数组 nums。你需要计算数组中所有非空连续子数组的和，然后将这些和按非递减顺序排序，创建一个包含 n * (n + 1) / 2 个数字的新数组。

返回新数组中从索引 left 到索引 right（从 1 开始索引）的数字之和（包含边界）。由于答案可能很大，请将其对 10^9 + 7 取模后返回。

示例 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]。从索引 1 到索引 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]。从索引 3 到索引 4 的数字之和为 3 + 3 = 6。

示例 3：

输入：nums = [1,2,3,4], n = 4, left = 1, right = 10
输出：50

约束条件：

  • n == nums.length
  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 100
  • 1 <= left <= right <= n * (n + 1) / 2

解题思路

这个问题需要我们计算所有连续子数组的和，然后排序，最后求指定范围内的元素和。

方法分析

方法一：暴力解法（推荐） 由于数组长度最大为1000，我们可以直接枚举所有子数组：

  1. 使用双重循环计算所有连续子数组的和
  2. 将这些和存储在数组中并排序
  3. 计算指定范围内元素的和

这种方法时间复杂度为O(n²log(n²))，在给定约束下完全可行。

方法二：优化方法 虽然可以使用优先队列或二分查找等高级技巧来优化，但考虑到约束条件和代码复杂度，直接的暴力方法已经足够高效。

实现要点：

  • 使用前缀和优化子数组和的计算
  • 注意取模操作避免溢出
  • 索引从1开始，需要相应调整

代码实现

class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        vector<int> sums;
        const int MOD = 1e9 + 7;
        
        // 计算所有子数组的和
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                sums.push_back(sum);
            }
        }
        
        // 排序
        sort(sums.begin(), sums.end());
        
        // 计算范围和
        long long result = 0;
        for (int i = left - 1; i < right; i++) {
            result = (result + sums[i]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        MOD = 10**9 + 7
        sums = []
        
        # 计算所有子数组的和
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                sums.append(current_sum)
        
        # 排序
        sums.sort()
        
        # 计算范围和
        result = 0
        for i in range(left - 1, right):
            result = (result + sums[i]) % MOD
        
        return result

public class Solution {
    public int RangeSum(int[] nums, int n, int left, int right) {
        List<int> sums = new List<int>();
        const int MOD = 1000000007;
        
        // 计算所有子数组的和
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                sums.Add(sum);
            }
        }
        
        // 排序
        sums.Sort();
        
        // 计算范围和
        long result = 0;
        for (int i = left - 1; i < right; i++) {
            result = (result + sums[i]) % MOD;
        }
        
        return (int)result;
    }
}

var rangeSum = function(nums, n, left, right) {
    const MOD = 1e9 + 7;
    const sums = [];
    
    // 计算所有子数组的和
    for (let i = 0; i < n; i++) {
        let sum = 0;
        for (let j = i; j < n; j++) {
            sum += nums[j];
            sums.push(sum);
        }
    }
    
    // 排序
    sums.sort((a, b) => a - b);
    
    // 计算范围和
    let result = 0;
    for (let i = left - 1; i < right; i++) {
        result = (result + sums[i]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n² log(n²)) = O(n² log n)
空间复杂度O(n²)

说明：

  • 时间复杂度：生成所有子数组和需要 O(n²)，排序需要 O(n² log n)，计算结果需要 O(right - left + 1)，总体为 O(n² log n)
  • 空间复杂度：需要存储 n*(n+1)/2 个子数组和，即 O(n²)