子数组和排序后的区间和 图解题解

排序后取第 left 到 right 个，要返回哪个和

给一个全是正整数的数组 nums，先把它所有非空连续子数组各自求和——长度 n 的数组一共有 n×(n+1)/2 个这样的和。把这些和从小到大排成一个新序列，返回新序列里下标 left 到 right（从 1 数起、含两端）这一段的总和，对 10⁹+7 取模。题面 nums=[1,2,3,4]、left=1、right=5 时答案是 13：排序后前 5 个数正好加到 13。

n 最多 1000，把全部子数组和排一遍贵不贵

n 最大只有 1000，子数组和总共 n×(n+1)/2 个，满打满算约 50 万个数。把它们全枚举出来是双重循环、约 O(n²)；对这约 n² 个数排序是 O(n²log n)，大概两千万次比较；再扫一段区间求和。三步里排序最重，合起来 O(n²log n)，这个量级现代机器一秒内跑得完。所以不必绕开枚举去凑更巧的公式，照题意把全部子数组和摆出来、排好、取区间，就够通过。

枚举每个子数组和，真要每段从头加一遍吗

枚举时有个白费力气的地方：固定起点 i，子数组 [i..j] 的和其实就是 [i..j−1] 的和再加上 nums[j] 一个数。要是每延伸一格都从 i 重新累加到 j，同一段前缀会被反复加许多遍。用一个累加变量 s 顶着：起点 i 处 s 归零，内层 j 从 i 往右走，每步 s 加上 nums[j] 就是当前子数组的和，直接记下来。这样每个子数组和只多做一次加法，枚举这步稳定在 O(n²)。

排好序之后，取哪一段、下标怎么减

排好序只是普通升序，真正要小心的是取哪一段。题目的 left、right 从 1 数起，数组下标却从 0 起，要取的是下标 left−1 到 right−1 这一段，忘了减 1 整段区间就整体偏一位，取到的是错的几个数。取出这段后把它们加起来，就是排序前那些子数组和里、第 left 小到第 right 小的总和。

[1,2,3,4] 上 left=1、right=5 算出什么

第一个数当起点：累加变量从 0 起，依次加成 1、3、6、10（对应 [1]、[1,2]、[1,2,3]、[1,2,3,4]）。换第二个数起头，归零后加成 2、5、9；从第三个起得 3、7；从第四个起得 4。收齐 10 个和：1、3、6、10、2、5、9、3、7、4。升序排好是 1、2、3、3、4、5、6、7、9、10，两个 3 各占一格。left=1、right=5 换成下标 0 到 4，取出 1、2、3、3、4，加起来 13，没超过取模上限，答案就是 13。

相等的和别去重，取模也别拖到最后

整套下来时间 O(n²log n)、空间 O(n²)，大头是装下约 n² 个子数组和的那个数组。边界想清三种：子数组只剩单个元素时和就是它自己；left=right 时区间只取排序后那一个数；left=1、right=n×(n+1)/2 时区间盖住全部，答案是所有子数组和之和。还有两处松了就悄悄错：排序时把相等的和去掉一个，长度就少一格、整段跟着错位——本例两个 3 必须都留；取模若拖到最后一次做，区间数一多累计和会先超出整型上限，得边加边对 10⁹+7 取模。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def rangeSum(self, nums: List[int], n: int, left: int, right: int) -> int:
        arr = []
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += nums[j]
                arr.append(s)
        arr.sort()
        mod = 10**9 + 7
        return sum(arr[left - 1 : right]) % mod

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        int arr[n * (n + 1) / 2];
        for (int i = 0, k = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += nums[j];
                arr[k++] = s;
            }
        }
        sort(arr, arr + n * (n + 1) / 2);
        int ans = 0;
        const int mod = 1e9 + 7;
        for (int i = left - 1; i < right; ++i) {
            ans = (ans + arr[i]) % mod;
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int rangeSum(int[] nums, int n, int left, int right) {
        int[] arr = new int[n * (n + 1) / 2];
        for (int i = 0, k = 0; i < n; ++i) {
            int s = 0;
            for (int j = i; j < n; ++j) {
                s += nums[j];
                arr[k++] = s;
            }
        }
        Arrays.sort(arr);
        int ans = 0;
        final int mod = (int) 1e9 + 7;
        for (int i = left - 1; i < right; ++i) {
            ans = (ans + arr[i]) % mod;
        }
        return ans;
    }
}