1508-子数组和排序后的区间和(Range Sum of Sorted Subarray Sums)

原文链接: https://leetcode-cn.com/problems/range-sum-of-sorted-subarray-sums

英文原文

You are given the array nums consisting of n positive integers. You computed the sum of all non-empty continuous subarrays from the array and then sorted them in non-decreasing order, creating a new array of n * (n + 1) / 2 numbers.

Return the sum of the numbers from index left to index right (indexed from 1), inclusive, in the new array. Since the answer can be a huge number return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 5
Output: 13 
Explanation: All subarray sums are 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. After sorting them in non-decreasing order we have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 1 to ri = 5 is 1 + 2 + 3 + 3 + 4 = 13.

Example 2:

Input: nums = [1,2,3,4], n = 4, left = 3, right = 4
Output: 6
Explanation: The given array is the same as example 1. We have the new array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. The sum of the numbers from index le = 3 to ri = 4 is 3 + 3 = 6.

Example 3:

Input: nums = [1,2,3,4], n = 4, left = 1, right = 10
Output: 50

Constraints:

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

中文题目

给你一个数组 nums ，它包含 n 个正整数。你需要计算所有非空连续子数组的和，并将它们按升序排序，得到一个新的包含 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] 。下标从 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 。

示例 3：

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

提示：

1 <= nums.length <= 10^3
nums.length == n
1 <= nums[i] <= 100
1 <= left <= right <= n * (n + 1) / 2

通过代码

高赞题解

解题思路

找出排序后数组的第 $k$ 小的元素。
至于如何找出，可以参考第 378 题和 719 题的思路。为此我们首先构造出一个二维有序矩阵。
定义矩阵的元素 $A(i,j)$：原数组 $nums$ 的从第 $i$ 个元素到第 $j$ 个元素（下标从 1 开始）的和。
例如：关于题目中的示例 $[1,2,3,4]$，可以构造出如下的矩阵:
$$\begin{matrix} 1 & 3 & 6 & 10 \ & 2 & 5 & 9 \ & & 3 & 7 \ & & & 4 \end{matrix}$$
注意： 当 $j < i$ 时，矩阵中是没有元素的。
显然，这个矩阵 关于列号 $j$ 递增、关于行号 $i$ 递减。 因此我们可以用类似 378 题的思路（二分+双指针）来求排序后数组的第 $k$ 小元素。
下面是由 $[1,2,3,4,5,6,7,8,9,10]$ 构造出的矩阵的色阶图。假设我们要找所有的 $val < 20$ 的元素数量，我们只需要沿着图中的线走一遍即可。

提示： 解题时，我们不需要完整地构造出矩阵，我们只需要随时知道 $A(i,j)$ 即可。为了求出 $A(i,j)$，我们首先求出原数组的前缀和 $sums$，然后根据定义，$A(i,j) = sums[j] - sums[i-1]$。（代码中 $i$ 的下标从 $0$ 开始，因此写成了 $sums[j] - sums[i]$）。
求出排序后数组的前 $k$ 项和。
需要考虑一个细节：数组中的第 $k$ 小的元素可能有多个，比如 $…a,a,x,x,[x],x,c,d…$，第 k 小元素为 $x$。
这时的思路是：先求所有 严格小于 $x$ 的元素和 $S$ 和元素个数 $cnt$，然后再求等于 $x$ 的部分。

为求出元素和 $S$，我们先构造 “前缀和的前缀和” （即首行元素的前缀和 $ssums$）以供参考。
以示例 $[1,2,3,4]$ 所构造出的矩阵为例，
$$\begin{matrix} \textbf{ssums}: & \textbf{1} & \textbf{4} & \textbf{10} & \textbf{20} \ array:& 1 & 3 & 6 & 10 \ &→ & \textbf{[2} & \textbf{5]} & 9 \ && & 3 & 7 \ && & & 4 \end{matrix}$$
假设我们需要求矩阵的第 $2$ 行的第 $2 \sim 3$ 列 (下标从 $1$ 开始) 的元素和。
可以看出规律：待求元素 $2,5$ 和 首行元素 $3,6$ 相比，都差了一个 $1$。
因此，我们可以先求出首行的对应元素的和，然后再减去 $1 \times 元素的个数$：
$$\begin{aligned} res &= (ssums[3] - ssums[1]) - (3-2+1)\times sums[1] \ &= (10-1) - 2 \&= 7. \end{aligned} $$
推广到一般情况，求出矩阵中的第 $m$ 行的第 $a \sim b$ 列元素的和（下标从 $1$ 开始）的公式为：
$$res = (ssums[b] - ssums[a-1]) - (b-a+1) \times sums[m-1].$$

然后等于 $x$ 的部分呢？这部分答案是 $(k - cnt) \times x$。
最后的答案就是 $S + (k - cnt) \times x$。

为了避免溢出，答案和中间结果用 long (64位) 来存储。
算出答案。
我们定义 $F(x)$ 为排序后数组的前 $x$ 项和。根据定义，题目的答案就是 $F(right) - F(left-1)$。

不要忘记取模 1e9 + 7。

代码

class Solution {
public:
    int getCnt(long sums[], int n, int x) {
        int res = 0;
        for(int i = 0, p = 1; i < n; ++i) {
            while(p <= n && sums[p] - sums[i] <= x)
                ++p;
            res += p-1-i;
        }
        return res;
    }
    int getKth(long sums[], int n, int idx) {
        int l = 0, r = 1e5;
        while(l < r) {
            int mid = (l + r) / 2, cnt = getCnt(sums, n, mid);
            if(cnt < idx)
                l = mid + 1;
            else
                r = mid;
        }
        return l;
    }
    long F(long sums[], long ssums[], int n, int x) {
        long num = getKth(sums, n, x), res = 0, cnt = 0;
        for(int i = 0, p = 1; i < n; ++i) {
            while(p <= n && sums[p] - sums[i] < num)
                ++p;
            // 这里, 需要求出矩阵的第 i+1 行的第 i+1 ~ p-1 (下标从 1 开始)个数字的和
            // 带入公式，有 m = i+1, a = i+1, b = p-1, 得
            // res = ssums[b] - ssums[a-1] + (b-a+1)*sums[m-1]
            //     = ssums[(p-1)] - ssums[(i+1)-1] - (((p-1)-(i+1))+1)*sums[(i+1)-1]
            //     = ssums[p-1] - ssums[i] - (p-i-1)*sums[i].
            res += ssums[p-1] - ssums[i] - sums[i] * ((long)(p-1-i));
            cnt += p-1-i;
        }
        return res + (x-cnt)*num;
    }
    int rangeSum(vector<int>& nums, int n, int left, int right) {
        long sums[n+1]; // 前缀和
        sums[0] = 0;
        for(int i = 0; i < n; ++i)
            sums[i+1] = sums[i] + nums[i];

        long ssums[n+1]; // 前缀和的前缀和
        ssums[0] = 0;
        for(int i = 0; i < n; ++i)
            ssums[i+1] = ssums[i] + sums[i+1];
        
        return (F(sums, ssums, n, right) - F(sums, ssums, n, left-1)) % ((long)(1e9 + 7));
    }
};

统计信息

通过次数	提交次数	AC比率
6298	11387	55.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途