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

这道题到底在问什么

输入

nums=[1,2,3,4], left=1, right=5

输出

13

输入

nums=[1,2,3,4], left=3, right=4

输出

6

先想最直接的笨办法

记住三步走:枚举出全部子数组和、升序排序、把下标 left 到 right 这一段加起来取模。下面每一帧都在走这三步。（动画第 3 步）

最优解：一步一步想明白

1. 3记住三步走:枚举出全部子数组和、升序排序、把下标 left 到 right 这一段加起来取模。下面每一帧都在走这三步。
2. 4上面这排是 nums = [1, 2, 3, 4]。右边面板用来收集所有子数组的和,现在还是空的。我们要枚举的是连续子数组,做法是固定一个起点 i,从 i 往右逐格延伸。一共会得到 4 乘 5 除以 2,也就是 10 个子数组和。
3. 5换一个新起点,i = 0。累加变量先归零,加上 nums[0] = 1,得到只含一个元素的子数组 [1],和是 1。把 1 记进面板。
4. 6从起点 0 继续往右延伸到下标 1。新进来的数是 nums[1] = 2,直接接到上一段的和 1 上,1 加 2 等于 3。这就是子数组 [1, 2] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
5. 7从起点 0 继续往右延伸到下标 2。新进来的数是 nums[2] = 3,直接接到上一段的和 3 上,3 加 3 等于 6。这就是子数组 [1, 2, 3] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
6. 8从起点 0 继续往右延伸到下标 3。新进来的数是 nums[3] = 4,直接接到上一段的和 6 上,6 加 4 等于 10。这就是子数组 [1, 2, 3, 4] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
7. 9换一个新起点,i = 1。累加变量先归零,加上 nums[1] = 2,得到只含一个元素的子数组 [2],和是 2。把 2 记进面板。
8. 10从起点 1 继续往右延伸到下标 2。新进来的数是 nums[2] = 3,直接接到上一段的和 2 上,2 加 3 等于 5。这就是子数组 [2, 3] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
9. 11从起点 1 继续往右延伸到下标 3。新进来的数是 nums[3] = 4,直接接到上一段的和 5 上,5 加 4 等于 9。这就是子数组 [2, 3, 4] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
10. 12换一个新起点,i = 2。累加变量先归零,加上 nums[2] = 3,得到只含一个元素的子数组 [3],和是 3。把 3 记进面板。
11. 13从起点 2 继续往右延伸到下标 3。新进来的数是 nums[3] = 4,直接接到上一段的和 3 上,3 加 4 等于 7。这就是子数组 [3, 4] 的和,记进面板。注意这里复用了上一段的结果,没有从头重算。
12. 14换一个新起点,i = 3。累加变量先归零,加上 nums[3] = 4,得到只含一个元素的子数组 [4],和是 4。把 4 记进面板。
13. 15枚举结束。把面板里的 10 个子数组和按生成顺序铺到舞台上,是 1、3、6、10、2、5、9、3、7、4。从这一帧起,舞台上摆的就是这排子数组和,原来的 nums 退到幕后。下一步要把它们排序。
14. 16把这 10 个数从小到大排好。原来的顺序 1、3、6、10、2、5、9、3、7、4,排完变成 1、2、3、3、4、5、6、7、9、10。这一步就是普通的升序排序,语言自带的排序函数即可。排好之后,我们才能按题目要求用下标去取区间。
15. 17提醒一个容易忽略的点:子数组 [3] 和子数组 [1, 2] 的和都是 3,排序后这两个 3 各自占一格,不会去重。绿色高亮的就是这两个 3,它们落在下标 2 和下标 3。题目要的是带重复的完整序列,千万别当成集合去掉重复。
16. 18现在做第三步,区间求和。题目的下标从 1 开始,left = 1、right = 5。换算到我们这从 0 开始的数组,就是下标 0 到下标 4,一共 5 个数。底色框住的就是要相加的这一段。这个减 1 的换算很关键,别搞错。
17. 19把下标 0 上的数 1 加进来。之前累计是 0,加上 1 得到 1。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
18. 20把下标 1 上的数 2 加进来。之前累计是 1,加上 2 得到 3。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
19. 21把下标 2 上的数 3 加进来。之前累计是 3,加上 3 得到 6。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
20. 22把下标 3 上的数 3 加进来。之前累计是 6,加上 3 得到 9。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。继续往右加下一格。
21. 23把下标 4 上的数 4 加进来。之前累计是 9,加上 4 得到 13。绿色部分就是已经累加进去的范围,紫色是这一帧刚加入的格子。到这,区间里 5 个数全部加完。
22. 24区间求和结束。排序后下标 1 到 5 是 1、2、3、3、4,加起来是 13。本例没有超过取模上限,所以对 10 的 9 次方加 7 取模后还是 13。这就是最终答案。回顾一下全流程:枚举全部子数组和、升序排序、再把指定区间加起来取模,三步走完。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问